The Bondy-Chvatal Theorem states that a graph is Hamiltonian if and only if its closure is Hamiltonian, where the closure is formed by repeatedly adding an edge between any two nonadjacent vertices whose degrees sum to at least the total number of vertices, until no more such edges can be added. Named for John Adrian Bondy and Vaclav Chvatal, it unifies earlier sufficient conditions for Hamiltonicity, including Dirac's Theorem and Ore's Theorem, as special cases of a single closure criterion.
Facts
Classification
Statement FormCharacterization Theorem 1 StatementA graph is Hamiltonian if and only if its closure is Hamiltonian. 1 Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Source Hamiltonian path (Wikipedia)
Sources
1. Bondy-Chvatal theorem, Wikipedia
Statement sectionQuote, Statement section
A graph is Hamiltonian if and only if its closure is Hamiltonian.
Hamiltonian path (Wikipedia)
In Branch: Graph Theory, Lead sentenceQuote, In Branch: Graph Theory, Lead sentence
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph tha
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.