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.