TOPICS
Search

Chvátal's Theorem


Let a graph G have graph vertices with vertex degrees d_1<=...<=d_m. If for every i<n/2 we have either d_i>=i+1 or d_(n-i)>=n-i, then the graph is Hamiltonian.


See also

Hamiltonian Graph

Explore with Wolfram|Alpha

References

Chvátal, V. "On Hamilton's Ideals." J. Combin. Th. 12, 163-168, 1972.

Referenced on Wolfram|Alpha

Chvátal's Theorem

Cite this as:

Weisstein, Eric W. "Chvátal's Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ChvatalsTheorem.html

Subject classifications