Past exam of the Probability, statistics and options II course of the University of Oxford / 2011 / R / R2 / a / i / Solution

Suppose a graph satisfying Ore's theorem were not Hamiltonian. Extend it, on the same vertices, to an edge-maximal non-Hamiltonian graph $H$. Adding edges preserves the degree-sum hypothesis. The complete graph is Hamiltonian, so $H$ has a missing edge $uv$. By maximality, $H+uv$ has a Hamiltonian cycle, which must use the new edge. Removing it gives a Hamiltonian path in $H$, labelled $u=v_1,v_2,\dots ,v_n=v$.

If some $i$ has both edges $u{v}_{i+1}$ and $v{v}_i$, the path can be closed into the cyclecontradicting the choice of $H$. Thus the index sets $\{i:u{v}_{i+1}\in E(H)\}$ and $\{i:v{v}_i\in E(H)\}$ are disjoint subsets of $\{1,\dots ,n-1\}$. Their sizes are ${\mathrm{deg}}_{H}u$ and ${\mathrm{deg}}_{H}v$. Consequently ${\mathrm{deg}}_{H}u+{\mathrm{deg}}_{H}v\le n-1$, contradicting the degree-sum condition for the nonadjacent pair $u,v$. Hence the original graph is Hamiltonian.