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


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.

Subject classifications