Ore's theorem
From Wikipedia, the free encyclopedia
For Ore's Theorem in ring theory, see Ore condition.
Ore's Theorem is a result in graph theory due to Øystein Ore (1960). It gives a sufficient condition for a graph to be Hamiltonian. Essentially it says that if a graph is "connected enough" then it must have a Hamilton cycle; in particular, we consider the number of edges incident to non-adjacent vertices.
[edit] Statement of the theorem
If G is a simple graph with n vertices, where 
, and if for each pair of non-adjacent vertices v and w, 
, then G is Hamiltonian.
Ore's Theorem is a generalisation of Dirac's Theorem; further generalisation leads to the Bondy-Chvátal theorem.
