Definition. ham cycle: a cycle consisting of all the vertices.
Proposition. There is a graph on \(n\) vertices with \(\binom{n-1}{2}+1\) edges that does not contain a ham-cycle
Proof. \(n-1\)-clique adjoin a vertex with a single edge to the clique.
Theorem. Any graph on \(n\) vertices with at least \(\binom{n-1}{2}+2\) edges contains a ham-cycle.
Proof. If the graph is \(K_n\) we are done. Assume the graph is not \(K_n\). Let \(v_0\) be the minimal degree vertex. We have \(\deg(v_0)\ge 2, \deg(v_0)\le n-2\).
We consider two cases: - Case 1: \(G[V\setminus v_0]\) has at least \(\binom{n-2}{2}+2\) edges. Then we are done by recursion, and splicing \(v_0\) into whatever cycle we find in \(G[V\setminus v_0]\). - Case 2: \(G[V\setminus v_0]\) has at most \(\binom{n-2}{2}+1\) edges. Actually, this is impossible, because it would imply that \[\deg(v_0) \ge \binom{n-1}{2}-\binom{n-2}{2}+1 = n-1,\] but we assumed that \(G\neq K_n\).