The Chvatal-Erdos Theorem gives a sufficient condition for a graph to contain a Hamiltonian cycle, a cycle visiting every vertex exactly once, stating that this holds whenever the graph's vertex connectivity is at least as large as its independence number. Named for Vaclav Chvatal and Paul Erdos, it is one of the standard sufficient conditions for Hamiltonicity, a property that in general is hard to determine for an arbitrary graph.
Facts
StatementIf there exists an s such that a given graph is s-vertex-connected and has no (s + 1)-vertex independent set, the graph must be Hamiltonian. 1 Classification
Statement Form Connections
Sources
1. Vaclav Chvatal, Wikipedia
Section on the 1972 paper with ErdosQuote, Section on the 1972 paper with Erdos
if there exists an s such that a given graph is s-vertex-connected and has no (s + 1)-vertex independent set, the graph must be Hamiltonian.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.