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 consisted of points and lines will have been made. Find all possible 'n' that will make a hamiltonian circuit exist for the given graph
Problem
Source: Korean MO winter camp 2020, Test 1 P8
Tags: graph theory, KMO, combinatorics
07.09.2020 16:41
This is 2020 Korean MO winter camp Test 1 P8.
07.09.2020 16:47
Thx for correcting
08.09.2020 18:00
$\cal G $ is a bipartite and planar. $\cal G$ is $\text {2-connected} $ and a circuit always exists for $n=2.$ Any pair of line interesct exactly once. There are no circuits for $n=1,3,4. $ This type of line collection offers a counter eg. forall $n\ge 3$ First $3$ black lines are added first then keep adding more rainbow paths.
08.09.2020 19:18
The problem is: Find all possible $n$ such that there exists a hamiltonian circuit for some graph. (You can choose the $n$ lines)
18.03.2021 17:14
n=1,2(mod 4),$n\ge 2$.
20.03.2021 13:09
See here for a proof.