Ore's theorem

Ore's theorem. In the mathematical field of graph theory, Ore's theorem is a fundamental result about the existence of Hamiltonian paths in finite graphs. It provides a sufficient condition based on the degrees of non-adjacent vertices, generalizing an earlier result by Gabriel Andrew Dirac. The theorem is a cornerstone in the study of Hamiltonian graphs and has inspired numerous related results in extremal graph theory.

Statement of the theorem

The theorem states that for a simple graph with \(n \geq 3\) vertices, if for every pair of distinct non-adjacent vertices the sum of their degrees is at least \(n\), then the graph contains a Hamiltonian cycle. This condition is often described as the Ore condition. The result directly implies that any graph satisfying this degree sum condition is a Hamiltonian graph. The bound of \(n\) is sharp, as demonstrated by certain families of non-Hamiltonian graphs like the Petersen graph for \(n=10\). The theorem is closely tied to concepts like vertex connectivity and the closure of a graph.

Proof sketch

A standard proof uses the technique of proof by contradiction and considers a maximal non-Hamiltonian graph that satisfies the degree condition. One assumes a graph \(G\) meets the hypothesis but lacks a Hamiltonian cycle. By adding edges without creating a Hamiltonian cycle, one can obtain a maximal counterexample. In such a maximal graph, there exists a Hamiltonian path \(v_1 v_2 \ldots v_n\) between some pair of non-adjacent vertices \(v_1\) and \(v_n\). The degree sum condition is then applied to the sets of neighbors of \(v_1\) and \(v_n\) along this path. A combinatorial argument, often involving the pigeonhole principle, shows that there must exist an index \(i\) such that \(v_1\) is adjacent to \(v_{i+1}\) and \(v_n\) is adjacent to \(v_i\), allowing the construction of a Hamiltonian cycle, contradicting the assumption. This method is a classic example of the extremal principle in action.

Applications and examples

Ore's theorem is frequently applied to prove that certain dense graphs are Hamiltonian. For instance, any complete graph \(K_n\) for \(n \geq 3\) trivially satisfies the condition and is Hamiltonian. The theorem also guarantees Hamiltonian cycles in many network models and tournaments with high minimum degree. It provides a quick check for the Hamiltonicity of graphs arising in scheduling theory, such as certain round-robin tournament schedules. The result is used in algorithm design, particularly for heuristics in the traveling salesman problem, which seeks a Hamiltonian cycle of minimum weight. Examples of graphs satisfying Ore's condition include Dirac's graphs where each vertex has degree at least \(n/2\), and certain power graphs of cycles.

Related results

Ore's theorem is a direct generalization of Dirac's theorem, which requires each vertex to have degree at least \(n/2\). A stronger sufficient condition was given by László Lovász and involves graph toughness. The Bondy–Chvátal theorem, a major extension, introduced the concept of the closure of a graph, showing that a graph is Hamiltonian if and only if its closure is Hamiltonian. Other related results include Pósa's theorem on degree sequences and the Chvátal's toughness conjecture. The Hajnal–Szemerédi theorem on equitable coloring and the Fan condition for Hamiltonian cycles are also part of this rich theoretical landscape. Research in this area often intersects with Ramsey theory and the study of random graphs.

History and context

The theorem was published in 1960 by the Norwegian mathematician Øystein Ore in his paper "Note on Hamilton Circuits" in the American Mathematical Monthly. Ore was a prominent figure in combinatorics and number theory, having also worked on structures like Möbius inversion and lattice theory. His result built directly upon the 1952 theorem of Gabriel Andrew Dirac, a British mathematician and the son of the physicist Paul Dirac. The search for sufficient conditions for Hamiltonian cycles has been a central theme in graph theory since the work of William Rowan Hamilton on the Icosian game. Subsequent developments by John Adrian Bondy, Václav Chvátal, and Paul Erdős have deeply explored the interface between degree conditions and cycle structure. The theorem remains a staple in textbooks like those by Béla Bollobás and Douglas B. West. Category:Graph theory Category:Mathematical theorems Category:Combinatorics