$n$ lines in a plane, proper coloring of intersection points with just 3 colors

Question

Draw $n$ lines in a plane so that there are no parallel lines and there are no three lines passing through the same point.

Each intersection point is colored red, green or blue. Prove that it is possible to color all intersection points in a “proper” way, so that any two adjacent points (like $A_i, A_j$) have different colors.

This also means that if you "travel" along an arbitrary line, you will cross $n-1$ intersection points, constantly changing colors from one intersection point to another.

My first (and last) try was to use induction. Obviously for two or three lines, we have one or three intersection points and with three colors available we have the base of induction proved. However, the induction step is more difficult. I was able to prove the induction step if in every possible arrangement of lines it was possible to find a line that divides the plane into two halves with one half having no intersection points. However, I was able to construct counter-examples where such line does not exist.

The last time I tried to solve a similar red-green-blue problem I discovered Ramsey theory. I wonder what I will discover this time :)

Answer 1

Let us assume WLOG that no lines are vertical--if not rotate the plane to make this so [make sure you see that this is indeed possible].

Let us colour the set of points from left to right [no lines are vertical, thus for each line $L$ there is indeed a strict ordering of the points on $L$ from left to right], with the colours 1,2,or 3, as follows.

1. Colour a leftmost point with the color 1. [As there are only $<n^2$ points there is indeed a leftmost point. Pick one such point arbitrarily]

2. Let $p$ be a point that satisfies the following: Letting $L_1$ and $L_2$ be the two lines containing $p$ [as only two lines intersect a point there are only two such $L_i$], all points to the left of $p$ on $L_1$ [which recall neither $L_1$ nor $L_2$ is not vertical] have already been colored and all points to the left of $p$ on $L_2$ have already been colored. Then letting $p_i$ be the point immediately to the left of $p$ on $L_i$; $i=1,2$; and writing as $c(p_i)$ the color assigned to $p_i$ for $i=1,2$ [$c(p_i) \in \{1,2,3\}$], let the color $c(p)$ of $p$ be an integer in $\{1,2,3\}$ that is neither $c(p_1)$ nor $c(p_2)$. [There indeed always exists such a $p$ as long as there are still uncoloured points, as a leftmost point of the points not coloured yet always suffices.]

See for yourself that the above algorithm indeed terminates, and that it also terminates with a proper 3-colouring.

Answer 2

One can prove this using the Szekeres-Wilf Theorem: For a graph $G$, $$\chi(G) \le 1 + \max_{H\subseteq G} \delta(H).$$

Indeed, it can be shown that any subgraph of the given graph has a vertex of degree at most $2$ (look at the "right-most" vertex.)

For reference, see West's Introduction to Graph Theory Section $5.1$ Pg $196$ for a proof of the Szekeres-Wilf Theorem.