# Prove or disprove that a graph made by $n$ straight lines is Hamiltonian.

Given $n$ lines, no two of which are parallel and no more than two intersect at the same point. Construct a graph with the intersection of lines as vertices and the line segments as edges. Prove or disprove that this graph is Hamiltonian.

I checked this for many graphs of different sizes and in every case, I could find a Hamiltonian cycle. I know that for n lines, the number of vertices will be n(n-1)/2 and edges n(n-2). I have no clue how to use this information and how to proceed further.

• Welcome to Maths Stack Exchange ! It is very important that you comment your question, what have you done, where are you blocked... – Jean Marie May 26 '17 at 6:33
• I checked this for many graphs of different sizes and in every case, I could find a Hamiltonian cycle. I know that for n lines, the number of vertices will be n(n-1)/2 and edges n(n-2). I have no clue how to use this information and how to proceed further. – Mukul Verma May 26 '17 at 6:43
• See this thesis (depositonce.tu-berlin.de/bitstream/11303/5993/4/…) and the theorem of Tutte (en.wikipedia.org/wiki/Hamiltonian_path) – Jean Marie May 26 '17 at 7:03
• Hint: Proceed by induction in $n$. The base case, $n=3$, is obvious. In the inductive step, one must consider how the $n+1$th line can be placed. – Hans Hüttel May 26 '17 at 7:36
• I would add (if this is the intended setting) that this collection of lines/line segments lies in a common plane. This is suggested by the requirement of "no parallel lines" but it would be best to make this an explicit part of the setup. – hardmath Jun 16 '17 at 1:16