The Bondy-Chvátal Theorem says a graph is Hamiltonian exactly when its closure is Hamiltonian. In combinatorics, you use it by adding edges between non-adjacent vertices whose degree sum is at least the number of vertices.
The Bondy-Chvátal Theorem is a graph theory result in combinatorics that turns a hard Hamiltonian-cycle question into a cleaner one. Instead of trying to spot a Hamiltonian cycle directly, you build the graph's closure by repeatedly adding an edge between any two non-adjacent vertices whose degrees add up to at least n, where n is the number of vertices. The theorem says this process does not change whether the graph is Hamiltonian.
That sounds small, but it is a big shortcut. Hamiltonian cycle problems are usually tough because there is no simple one-step test that works for every graph. Bondy-Chvátal gives you a way to strengthen the graph without changing the answer, so a graph that looks messy can become easier to reason about after closure.
Here is the idea in plain terms: if two vertices are not connected, but both already have lots of incident edges, then they are “close enough” to behave like a missing edge for Hamiltonian purposes. The degree-sum condition, deg(u) + deg(v) >= n, is the trigger. If that condition holds, you may add uv in the closure process.
The theorem comes in two useful pieces. First, every added edge preserves Hamiltonicity. Second, the final closure graph is Hamiltonian if and only if the original graph is Hamiltonian. So if you can show the closure has a Hamiltonian cycle, you are done. This is why the theorem is often used as a proof tool, not just a definition.
A compact way to think about it is this: Bondy-Chvátal does not tell you exactly where the cycle is, but it tells you which missing edges are safe to pretend exist. That makes it a strong bridge between local degree information and the global structure of a Hamiltonian cycle.
One common mistake is to read the theorem as saying every graph with a high-degree pair is Hamiltonian. That is not what it says. You still need to look at the whole closure process, because the theorem is about preserving Hamiltonicity, not magically creating it from one edge test alone.
Bondy-Chvátal shows up whenever combinatorics turns a global traversal problem into a degree-based check. Hamiltonian cycles are about visiting every vertex exactly once and returning to the start, which is much harder than checking an Eulerian condition. The theorem gives you one of the cleanest ways to use local information, vertex degrees, to make a global conclusion.
This matters because many graphs in class problems do not look obviously Hamiltonian. You may be given a network, a bipartite-style construction, or a graph with a few missing edges, and the direct search for a cycle is messy. Closure lets you simplify the graph step by step while keeping the Hamiltonian answer unchanged. If the closure becomes complete enough to make a cycle obvious, the original graph inherits that result.
It also connects nicely to other graph theory tools. Degree conditions like Ore's Theorem are nearby ideas, and Bondy-Chvátal helps explain why those conditions work. You are not just memorizing a test, you are seeing the logic behind why degree sums can force a Hamiltonian cycle.
In a course setting, this theorem is a proof strategy as much as a result. You might use it to justify a claim about a graph class, compare Hamiltonian and Eulerian thinking, or explain why a certain network design can support a round-trip route that hits every vertex once.
Keep studying COMBINATORICS Unit 11
Visual cheatsheet
view galleryHamiltonian Cycle
Bondy-Chvátal is all about deciding whether a Hamiltonian cycle exists. The theorem does not replace the cycle itself, but it gives you a way to test Hamiltonicity by modifying the graph safely. If you can show the closure has a Hamiltonian cycle, then the original graph does too.
Graph Connectivity
Connectivity is a basic starting point for Hamiltonian questions, but it is not enough on its own. Bondy-Chvátal uses stronger local information, especially vertex degrees, to push beyond simple connectedness. A connected graph may still fail to be Hamiltonian unless the degree-sum pattern supports a cycle.
Ore's Theorem
Ore's Theorem is a famous degree-sum condition for Hamiltonian graphs, and Bondy-Chvátal generalizes that style of reasoning. Ore gives a direct sufficient condition, while Bondy-Chvátal explains the closure process behind it. If you know Ore, Bondy-Chvátal feels like the broader framework.
Depth-first search
Depth-first search is a traversal method, so it is useful for exploring graphs, but it does not decide Hamiltonicity by itself. Bondy-Chvátal is more structural: it tells you when you can safely add edges and preserve the Hamiltonian property. DFS may help you inspect a graph, but the theorem gives the actual guarantee.
A problem set question will usually ask you to decide whether a graph is Hamiltonian or to justify a claim using closure. The move is to check pairs of non-adjacent vertices, add any edge whose degree sum is at least n, and keep going until no more edges qualify. Then you analyze the closure graph instead of the original one.
If the closure is obviously Hamiltonian, you can conclude the original graph is Hamiltonian too. If not, the theorem does not prove the graph is non-Hamiltonian, so you need to be careful not to overclaim. A common quiz mistake is stopping after one added edge and treating that as a full proof.
You may also see short-answer prompts asking you to explain why a degree condition is enough, or to compare this theorem with Ore's Theorem. In those cases, focus on the idea that local degree totals can force a global cycle structure.
Ore's Theorem is a direct sufficient condition for a graph to be Hamiltonian when every non-adjacent pair has degree sum at least n. Bondy-Chvátal is broader: it uses the same degree-sum idea inside a closure process and says Hamiltonicity is preserved through added edges. Ore is a special case of the closure viewpoint.
Bondy-Chvátal Theorem is a closure theorem for Hamiltonian graphs in combinatorics.
You add an edge between non-adjacent vertices when their degree sum is at least the number of vertices in the graph.
The theorem says the original graph is Hamiltonian exactly when its closure is Hamiltonian.
It is most useful when a graph is hard to check directly, but its degree pattern suggests Hamiltonicity.
Do not treat one degree-sum check as a full proof unless you have finished the closure argument.
It is a theorem about Hamiltonian graphs and graph closure. In a graph with n vertices, you may add an edge between non-adjacent vertices when their degrees add to at least n, and this does not change whether the graph is Hamiltonian.
Start with the original graph and check every non-adjacent pair. If a pair has degree sum at least n, add that edge and keep repeating until no more edges qualify. Then test the closure graph for a Hamiltonian cycle.
No, but they are closely related. Ore's Theorem gives a direct degree-sum condition that guarantees Hamiltonicity, while Bondy-Chvátal uses the same idea inside the closure process. Ore can be seen as a special case of the broader closure idea.
Not by itself. If the closure does not reveal a Hamiltonian cycle, the theorem does not automatically tell you the graph is non-Hamiltonian. It is a tool for preserving Hamiltonicity, not a universal nonexistence test.