Ore's theorem

For Ore's theorem in ring theory, see Ore condition.

Ore's theorem is a result in graph theory proved in 1960 by Norwegian mathematician Øystein Ore. It gives a sufficient condition for a graph to be Hamiltonian, essentially stating that a graph with "sufficiently many edges" must contain a Hamilton cycle. Specifically, the theorem considers the sum of the degrees of any two non-adjacent vertices: if this sum is always at least equal to the total number of vertices in the graph, then the graph is Hamiltonian.

Formal statement

Let G be a (finite and simple) graph with n ≥ 3 vertices. We denote by deg v the degree of a vertex v in G, i.e. the number of incident edges in G to v. Then, Ore's theorem states that if

deg v + deg w ≥ n for every pair of non-adjacent vertices v and w of G (*)

then G is Hamiltonian.

Proof

Suppose it were possible to construct a graph that fulfils condition (*) which is not Hamiltonian. According to this supposition, let G be a graph on n ≥ 3 vertices that satisfies property (*), is not Hamiltonian, and has the maximum possible number of edges among all n-vertex non-Hamiltonian graphs that satisfy property (*). Because the number of edges was chosen to be maximal, G must contain a Hamiltonian path v₁v₂...v_n, for otherwise it would be possible to add edges to G without breaching property (*). Since G is not Hamiltonian, v₁ cannot be adjacent to v_n, for otherwise v₁v₂...v_n would be a Hamiltonian cycle. By property (*), deg v₁ + deg v_n ≥ n, and the pigeon hole principle implies that for some i in the range 2 ≤ i ≤ n − 1, v_i is adjacent to v₁ and v_{i − 1} is adjacent to v_n. But the cycle v₁v₂...v_{i − 1}v_nv_{n − 1}...v_i is then a Hamilton cycle. This contradiction yields the result.

Related results

Ore's theorem is a generalization of Dirac's theorem that, when each vertex has degree at least n/2, the graph is Hamiltonian. For, if a graph meets Dirac's condition, then clearly each pair of vertices has degrees adding to at least n.

In turn Ore's theorem is generalized by the Bondy–Chvátal theorem. One may define a closure operation on a graph in which, whenever two nonadjacent vertices have degrees adding to at least n, one adds an edge connecting them; if a graph meets the conditions of Ore's theorem, its closure is a complete graph. The Bondy–Chvátal theorem states that a graph is Hamiltonian if and only if its closure is Hamiltonian; since the complete graph is Hamiltonian, Ore's theorem is an immediate consequence.

Ore's theorem may also be strengthened to give a stronger condition than Hamiltonicity as a consequence of the degree condition in the theorem. Specifically, every graph satisfying the conditions of Ore's theorem is either a regular complete bipartite graph or is pancyclic (Bondy 1971).

References

• Bondy, J. A. (1971), "Pancyclic graphs I", Journal of Combinatorial Theory, Series B 11 (1): 80–84, doi:10.1016/0095-8956(71)90016-5 .
• Ore, Ø. (1960), "Note on Hamiltonian circuits", American Mathematical Monthly 67 (1): 55, JSTOR 2308928 .