1. Formal statement

2. Proof

3. Algorithm

4. Related results

5. References

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 {{math|G}} be a (finite and simple) graph with {{math|n ≥ 3}} vertices. We denote by {{math|deg v}} the degree of a vertex {{math|v}} in {{math|G}}, i.e. the number of incident edges in {{math|G}} to {{math|v}}. Then, Ore's theorem states that if

then {{math|G}} is Hamiltonian.

Proof

It is equivalent to show that every non-Hamiltonian graph {{mvar|G}} does not obey condition (∗). Accordingly, let {{mvar|G}} be a graph on {{math|n ≥ 3}} vertices that is not Hamiltonian, and let {{mvar|H}} be formed from {{mvar|G}} by adding edges one at a time that do not create a Hamiltonian cycle, until no more edges can be added. Let {{math|x}} and {{math|y}} be any two non-adjacent vertices in {{mvar|H}}. Then adding edge {{math|xy}} to {{mvar|H}} would create at least one new Hamiltonian cycle, and the edges other than {{math|xy}} in such a cycle must form a Hamiltonian path {{math|v₁v₂...v_n}} in {{mvar|H}} with {{math|1=x = v₁}} and {{math|1=y = v_n}}. For each index {{math|i}} in the range {{math|2 ≤ i ≤ n}}, consider the two possible edges in {{mvar|H}} from {{math|v₁}} to {{math|v_i}} and from {{math|v_{i − 1}}} to {{math|v_n}}. At most one of these two edges can be present in {{mvar|H}}, for otherwise the cycle {{math|v₁v₂...v_{i − 1}v_nv_{n − 1}...v_i}} would be a Hamiltonian cycle. Thus, the total number of edges incident to either {{math|v₁}} or {{math|v_n}} is at most equal to the number of choices of {{math|i}}, which is {{math|n − 1}}. Therefore, {{mvar|H}} does not obey property (∗), which requires that this total number of edges ({{math|deg v₁ + deg v_n}}) be greater than or equal to {{math|n}}. Since the vertex degrees in {{mvar|G}} are at most equal to the degrees in {{mvar|H}}, it follows that {{mvar|G}} also does not obey property (∗).

Algorithm

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 {{math|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 {{math|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 {{math|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 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 {{harv|Bondy|1971}}.

References

• {{citation

• {{Citation

• {{citation|first=Ø.|last=Ore|authorlink=Øystein Ore|title=Note on Hamilton circuits|journal=American Mathematical Monthly|volume=67|year=1960|page=55|issue=1|jstor=2308928|doi=10.2307/2308928}}.
• {{citation

• {{citation

• John Lawrence Ashberry
• John Lawrence Baird
• John Lawrence Baird, 1st Viscount Stonehaven
• John Lawrence Daly
• John Lawrence LeConte
• John Lawrence Le Conte
• John Lawrence Sullivan
• John Lawrence Toole
• John Lawrence Whitty
• John Lawrie
• John Laws
• John Laws (judge)
• John Law (sociologist)
• John Lawson (explorer)
• John Lawton (musician)
• John Laycock
• John Layfield
• John Layman
• John Lazarus (playwright)
• John L. Bell
• John L. Broome
• John L. Dagg
• John L. Dorsey
• John L. Dorsey, Jr.
• John L. Dorsey Jr.