4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Welcome to Maths Stack Exchange ! It is very important that you comment your question, what have you done, where are you blocked... $\endgroup$ – Jean Marie May 26 '17 at 6:33
  • $\begingroup$ 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. $\endgroup$ – Mukul Verma May 26 '17 at 6:43
  • 2
    $\begingroup$ See this thesis (depositonce.tu-berlin.de/bitstream/11303/5993/4/…) and the theorem of Tutte (en.wikipedia.org/wiki/Hamiltonian_path) $\endgroup$ – Jean Marie May 26 '17 at 7:03
  • 1
    $\begingroup$ 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. $\endgroup$ – Hans Hüttel May 26 '17 at 7:36
  • 1
    $\begingroup$ 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. $\endgroup$ – hardmath Jun 16 '17 at 1:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.