Korean MO winter camp 2020, Test 1 P8 problem I've come across a challenging graph theory problem. Roughly translated, it goes something like this:
There are $n$ lines drawn on a plane: no two lines are parallel to each other, and no three lines meet at a single point.
Those lines would partition the plane down into many 'area's. Suppose we select one point from each area. Also, should two areas share a common side, we connect the two points belonging to the respective areas with a line.
A graph consisting of points and lines will have been made. Find all possible $n$ such that a Hamiltonian circuit exist for the given graph.
This problem seems hard to solve: Today I tried to solve it but couldn't; the question is also posted here (on the Art of Problem Solving site) but no one has solved it, so I'm now asking here. Thanks.
 A: The graph is bipartite and has $\binom{n+1}{2}+1$ regions, so the problem can only be solvable when $\binom{n+1}{2}+1$ is even: when $n \equiv 1,2 \pmod 4$. This naturally suggests an induction step going from $n$ to $n+4$, adding four lines.
Here is our induction hypothesis: an $n$-line configuration where we assume that there is a Hamiltonian cycle. I've drawn all the vertices corresponding to the external regions, and I assume that the red edge I've drawn is a part of the Hamiltonian cycle. (This is done without loss of generality: some external regions have to have degree $2$, so they'll be adjacent to two other external regions in the cycle.)

Now, we add four more lines, as shown below, and extend the cycle with the orange vertices and edges:

This gives us an $(n+4)$-line configuration with a Hamiltonian cycle, as desired. You can see that although I've given a drawing with $n=5$, the thing I'm doing in the "grid" portion of the diagram in the bottom right extends to any $n>1$.
The base case $n=2$ is easy; $n=5$ is left as an exercise to the reader, because I drew it but forgot to save. (Make sure you start with a line configuration which, if you $2$-color the $16$ regions, has $8$ regions of each color.)
(Actually, one solution to $n=5$ almost follows from $n=1$, but not quite, because $n=1$ is an edge case and also doesn't have a Hamiltonian cycle.)
