TOPICS
Search

Dirac's Theorem


A simple graph with n>=3 graph vertices in which each graph vertex has vertex degree >=n/2 has a Hamiltonian cycle.


See also

Hamiltonian Cycle

Explore with Wolfram|Alpha

References

Dirac, G. "Some Theorems on Abstract Graphs." Proc. London Math. Soc. 2, 69-81, 1952.Li, H. "Generalizations of Dirac's Theorem in Hamiltonian Graph Theory--A Survey." Disc. Math. 313, 2034-2053, 2013.

Referenced on Wolfram|Alpha

Dirac's Theorem

Cite this as:

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

Subject classifications