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.
Let be a (finite and simple) graph with vertices. We denote by the degree of a vertex in , i.e. the number of incident edges in to . Then, Ore's theorem states that if
then is Hamiltonian.
It is equivalent to show that every non-Hamiltonian graph does not obey condition (âÂÂ). Accordingly, let be a graph on vertices that is not Hamiltonian, and let be formed from by adding edges one at a time that do not create a Hamiltonian cycle, until no more edges can be added. Let and be any two non-adjacent vertices in . Then adding edge to would create at least one new Hamiltonian cycle, and the edges other than in such a cycle must form a Hamiltonian path in with and . For each index in the range , consider the two possible edges in from to and from to . At most one of these two edges can be present in , for otherwise the cycle would be a Hamiltonian cycle. Thus, the total number of edges incident to either or is at most equal to the number of choices of , which is . Therefore, does not obey property (âÂÂ), which requires that this total number of edges () be greater than or equal to . Since the vertex degrees in are at most equal to the degrees in , it follows that also does not obey property (âÂÂ).
describes the following simple algorithm for constructing a Hamiltonian cycle in a graph meeting Ore's condition.
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<sub>j</sub> and v<sub>j + 1</sub> 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<sub>i</sub> and v<sub>i + 1</sub> 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<sup>2</sup>), matching the number of edges in the input graph.
Ore's theorem is a generalization of Dirac's theorem that, when each vertex has degree at least , the graph is Hamiltonian. For, if a graph meets Dirac's condition, then clearly each pair of vertices has degrees adding to at least .
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 , 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.
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 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 .