My lecture notes in Graph Theory states that a graph of order $n$ and with size (= number of edges) $\binom n 2-(n-2)$ is the maximal graph that does not contain a Hamiltonian cycle.

My question now is how to find such a graph? How can I construct a graph of order $n$ such that this is true?

For the proof that no greater size can be achieved there was a similar question on this site: Proving that a graph of a certain size is Hamiltonian

This can be used to prove that no greater size can be achieved, so I am not interested in this part, only in the constructon part.


Hint: If a vertex has degree 1, it can't be part of a cycle.

  • $\begingroup$ Thanks, I did not think of that, this explains the term $\binom n 2$, where does $n-2$ come from? $\endgroup$ Nov 9 '13 at 15:45
  • $\begingroup$ @UlrichOtto What is the degree of a vertex in a complete graph with $n$ vertices? $\endgroup$
    – Calvin Lin
    Nov 9 '13 at 15:46
  • $\begingroup$ Degree is $n-1$ $\endgroup$ Nov 9 '13 at 15:47
  • $\begingroup$ Oh ok, I have to exclude this case because complete graph contains Hamiltonian cycle, but there is still n-2 instead of n-1 $\endgroup$ Nov 9 '13 at 15:49
  • $\begingroup$ @UlrichOtto Read my hint ... What is $(n-1) - 1$? $\endgroup$
    – Calvin Lin
    Nov 9 '13 at 15:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.