= Ore's theorem
{c}
{title2=$d(u)+d(v)\geq n\text{ for nonadjacent }u,v$}
<Ore's theorem>, named after <Øystein Ore>, says that a finite simple <graph> with $n\geq3$ vertices is Hamiltonian if every nonadjacent pair has degree sum at least $n$.
For a proof, enlarge a hypothetical counterexample to an edge-maximal non-Hamiltonian graph. Adding a missing edge $uv$ creates a <Hamiltonian cycle>, hence the original graph has a Hamiltonian path $u=v_1,\ldots,v_n=v$. If both $uv_{i+1}$ and $vv_i$ are edges, the path closes to a cycle by reversing its final segment. Thus the index sets of these two kinds of edges are disjoint in $\{1,\ldots,n-1\}$, giving $d(u)+d(v)\leq n-1$, a contradiction. The degree condition is sufficient and need not follow from a lower bound of $n/2$ on every individual degree.
Back to article page
