Ore's theorem

From Wikipedia, the free encyclopedia

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 n ≥ 3, and if for each pair of non-adjacent vertices v and w, deg(v) + deg(w) ≥ n, then G is Hamiltonian.

Ore's Theorem is a generalization of Dirac's Theorem; further generalization leads to the Bondy-Chvátal theorem.

[edit] See also

• Dirac's Theorem
• Bondy-Chvátal theorem

[edit] References

This article does not cite any references or sources. (January 2008) Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.