Hamiltonian graph

A Hamiltonian graph is a graph containing a Hamilton cycle. This describes existence of a spanning graph cycle, rather than requiring every edge of the graph to belong to that graph cycle. In the finite simple graph convention, $K_n$ is a Hamiltonian graph for $n\ge 3$, because any ordering of its vertices closes using available edges.

Ore's theorem, named after Øystein Ore, says that a finite simple graph with $n\ge 3$ 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,\dots ,v_n=v$. If both $u{v}_{i+1}$ and $v{v}_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,\dots ,n-1\}$, giving $d(u)+d(v)\le n-1$, a contradiction. The degree condition is sufficient and need not follow from a lower bound of $n/2$ on every individual degree.