Ore's theorem

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 \geq 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 \geq 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 \geq 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 1 v 2 ... v n$ , for otherwise it would be possible to add edges to $G$ without breaching property (*). Since $G$ is not Hamiltonian, $v 1$ cannot be adjacent to $v n$ , for otherwise $v 1 v 2 ... v n$ would be a Hamiltonian cycle. By property (*), $deg v 1 + deg v n \geq n$ , and the pigeon hole principle implies that for some $i$ in the range $2 \leq i \leq n - 1$ , $v i$ is adjacent to v₁ and $v i - 1$ is adjacent to $v n$ . But the cycle $v 1 v 2 ... v i - 1 v n v n - 1 ... v i$ is then a Hamilton cycle. This contradiction yields the result.

Algorithm

Palmer (1997) describes the following simple algorithm for constructing a Hamiltonian cycle in a graph meeting Ore's condition.

Arrange the vertices arbitrarily into a cycle, ignoring adjacencies in the graph.
While the cycle contains two consecutive vertices v_i and v_i + 1 that are not adjacent in the graph, perform the following two steps:
- Search for an index j such that the four vertices v_i, v_i + 1, v_j, and v_j + 1 are all distinct and such that the graph contains edges from v_i to v_j and from v_j + 1 to v_i + 1
- Reverse the part of the cycle between v_i + 1 and v_j (inclusive).

Each step increases the number of consecutive pairs in the cycle that are adjacent in the graph, by one or two pairs (depending on whether v_j and v_j + 1 are already adjacent), so the outer loop can only happen at most n times before the algorithm terminates, where n is the number of vertices in the given graph. By an argument similar to the one in the proof of the theorem, the desired index j must exist, or else the nonadjacent vertices v_i and v_i + 1 would have too small a total degree. Finding i and j, and reversing part of the cycle, can all be accomplished in time O(n). Therefore, the total time for the algorithm is O(n²), matching the number of edges in the input graph.

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.

Woodall (1972) found a version of Ore's theorem that applies to directed graphs. Suppose a digraph G has the property that, for every two vertices u and v, either there is a vertex from u to v or the outdegree of u plus the indegree of v equals or exceeds the number of vertices in G. Then, according to Woodall's theorem, G contains a directed Hamiltonian cycle. Ore's theorem may be obtained from Woodall by replacing every edge in a given undirected graph by a pair of directed edges.

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 Hamilton circuits", American Mathematical Monthly, 67 (1): 55, JSTOR 2308928.
Palmer, E. M. (1997), "The hidden algorithm of Ore's theorem on Hamiltonian cycles", Computers & Mathematics with Applications, 34 (11): 113–119, doi:10.1016/S0898-1221(97)00225-3, MR 1486890.
Woodall, D. R. (1972), "Sufficient conditions for circuits in graphs", Proceedings of the London Mathematical Society, Third Series, 24: 739–755, MR 0318000.