info prev up next book cdrom email home

Chvátal's Theorem

Let the Graph $G$ have Vertices with Valences $d_1\leq \dots \leq
d_m$. If for every $i<n/2$ we have either $d_i\geq i+1$ or $d_{n-i}\geq n-i$, then the Graph is Hamiltonian.




© 1996-9 Eric W. Weisstein
1999-05-26