Ore's theorem [SEP] named after
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 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 be a
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 .
References.
- .
- .