= 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,\ldots,v_n=v$.
If some $i$ has both edges $uv_{i+1}$ and $vv_i$, the path can be closed into the cycle
$$
v_1,v_2,\ldots,v_i,v_n,v_{n-1},\ldots,v_{i+1},v_1,
$$
contradicting the choice of $H$. Thus the index sets $\{i:uv_{i+1}\in E(H)\}$ and $\{i:vv_i\in E(H)\}$ are disjoint subsets of $\{1,\ldots,n-1\}$. Their sizes are $\deg_Hu$ and $\deg_Hv$. Consequently $\deg_Hu+\deg_Hv\leq n-1$, contradicting the degree-sum condition for the nonadjacent pair $u,v$. Hence the original <graph> is Hamiltonian.
Back to article page
