TOPICS
Search

Ore's Theorem


If a graph G has n graph vertices such that every pair of the n graph vertices which are not joined by a graph edge has a sum of valences which is >=n, then G is Hamiltonian.

A graph satisfying Ore's criterion is known as an Ore graph.


See also

Hamiltonian Graph, Ore Graph

Explore with Wolfram|Alpha

References

Bondy, J. A. "Pancyclic Graphs I." J. Combin. Th. 11, 80-84, 1971.Meyniel, M. "Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe orienté." J. Combin. Th. 14, 137-147, 1973.Ore, Ø. "Note on Hamilton Circuits." Amer. Math. Monthly 67, 55, 1960.Palmer, E. M. "The Hidden Algorithm of Ore's Theorem on Hamiltonian Cycles." Computers Math. Appl. 34, 113-119, 1997.Woodall, D. R. "Sufficient Conditions for Circuits in Graphs." Proc. London Math. Soc. 24: 739-755, 1972.

Referenced on Wolfram|Alpha

Ore's Theorem

Cite this as:

Weisstein, Eric W. "Ore's Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/OresTheorem.html

Subject classifications