# Maximal graph that does not contain Hamiltonian cycle

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.

• Thanks, I did not think of that, this explains the term $\binom n 2$, where does $n-2$ come from? Nov 9 '13 at 15:45
• @UlrichOtto What is the degree of a vertex in a complete graph with $n$ vertices? Nov 9 '13 at 15:46
• Degree is $n-1$ Nov 9 '13 at 15:47
• @UlrichOtto Read my hint ... What is $(n-1) - 1$? Nov 9 '13 at 15:50