Ore's theorem

File:Ore theorem example.svg

A graph meeting the conditions of Ore's theorem, and a Hamiltonian cycle in it. There are two vertices with degree less than n/2 in the center of the drawing, so the conditions for Dirac's theorem are not met. However, these two vertices are adjacent, and all other pairs of vertices have total degree at least seven, the number of vertices.

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 pairs of non-adjacent vertices: if every such pair has a sum that at least equals the total number of vertices in the graph, then the graph is Hamiltonian.

Formal statement

Let Template:Math be a (finite and simple) graph with Template:Math vertices. We denote by Template:Math the degree of a vertex Template:Math in Template:Math, i.e. the number of incident edges in Template:Math to Template:Math. Then, Ore's theorem states that if

then Template:Math is Hamiltonian.

Proof

File:Ore theorem proof.svg

Illustration for the proof of Ore's theorem. In a graph with the Hamiltonian path Template:Math but no Hamiltonian cycle, at most one of the two edges Template:Math and Template:Math (shown as blue dashed curves) can exist. For, if they both exist, then adding them to the path and removing the (red) edge Template:Math would produce a Hamiltonian cycle.

It is equivalent to show that every non-Hamiltonian graph Template:Mvar does not obey condition (∗). Accordingly, let Template:Mvar be a graph on Template:Math vertices that is not Hamiltonian, and let Template:Mvar be formed from Template:Mvar by adding edges one at a time that do not create a Hamiltonian cycle, until no more edges can be added. Let Template:Math and Template:Math be any two non-adjacent vertices in Template:Mvar. Then adding edge Template:Math to Template:Mvar would create at least one new Hamiltonian cycle, and the edges other than Template:Math in such a cycle must form a Hamiltonian path Template:Math in Template:Mvar with Template:Math and Template:Math. For each index Template:Math in the range Template:Math, consider the two possible edges in Template:Mvar from Template:Math to Template:Math and from Template:Math to Template:Math. At most one of these two edges can be present in Template:Mvar, for otherwise the cycle Template:Math would be a Hamiltonian cycle. Thus, the total number of edges incident to either Template:Math or Template:Math is at most equal to the number of choices of Template:Math, which is Template:Math. Therefore, Template:Mvar does not obey property (∗), which requires that this total number of edges (Template:Math) be greater than or equal to Template:Math. Since the vertex degrees in Template:Mvar are at most equal to the degrees in Template:Mvar, it follows that Template:Mvar also does not obey property (∗).

Algorithm

Template:Harvtxt describes the following simple algorithm for constructing a Hamiltonian cycle in a graph meeting Ore's condition.

1. Arrange the vertices arbitrarily into a cycle, ignoring adjacencies in the graph.
2. 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 Template:Math, the graph is Hamiltonian. For, if a graph meets Dirac's condition, then clearly each pair of vertices has degrees adding to at least Template:Math.

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 Template:Math, 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.

Template:Harvtxt 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 an edge 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. A closely related theorem by Template:Harvtxt states that an n-vertex strongly connected digraph with the property that, for every two nonadjacent vertices u and v, the total number of edges incident to u or v is at least 2n − 1 must be Hamiltonian.

Ore's theorem may also be strengthened to give a stronger conclusion 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 .

References

• .
• .
• .
• .
• .