From the Closure Rule to a Hamiltonicity Test
A Hamiltonian cycle visits every vertex exactly once before returning to its starting point. The Bondy–Chvátal closure gives a way to test for Hamiltonicity by adding certain missing edges and examining the resulting graph. The important detail in a computation is that degrees are taken in the graph as it currently stands: an edge added at one step can make another pair eligible at a later step.
All graphs considered here are finite and simple. Each step keeps the vertex set fixed and adds one edge, so it increases both endpoint degrees by \(1\) and leaves all other degrees unchanged. Since there are only \(\binom{n}{2}\) possible edges, the process must terminate after at most \(\binom{n}{2}-|E(G)|\) additions.
The result that makes this computation useful is the closure theorem. It applies to a graph and a nonadjacent pair whose degree sum, measured in that graph, is at least its order.
Applying the theorem at each step shows that the starting graph is Hamiltonian if and only if the terminal graph is Hamiltonian. In particular, if the terminal graph is complete and \(n\ge3\), then it has the Hamiltonian cycle \(1,2,\ldots,n,1\), after any labelling of its vertices. The original graph is therefore Hamiltonian as well. The added edges are part of the calculation; they need not belong to a Hamiltonian cycle in the original graph.
A Step-by-Step Closure Calculation
Worked Example: Completing the Closure of a Graph on Five Vertices
Let \(G\) have \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{14,15,23,24,25,34,35,45\}\). Its only nonedges are \(12\) and \(13\). We calculate degrees from the listed edges: vertex \(1\) is incident with \(14,15\), so its degree is \(2\); vertices \(2\) and \(3\) each have degree \(3\); vertices \(4\) and \(5\) each have degree \(4\).
| Stage | Degrees \((d(1),d(2),d(3),d(4),d(5))\) | Eligible nonedge and calculation |
|---|---|---|
| Initial graph | \((2,3,3,4,4)\) | \(12:\ 2+3=5\); \(13:\ 2+3=5\) |
| After adding \(12\) | \((3,4,3,4,4)\) | \(13:\ 3+3=6\) |
| After adding \(13\) | \((4,4,4,4,4)\) | No nonedges remain |
Both initial nonedges meet the threshold \(n=5\). Choose \(12\) first. Its addition raises the degrees of \(1\) and \(2\) by \(1\), giving \((3,4,3,4,4)\); now the remaining nonedge \(13\) has degree sum \(3+3=6\), so it can be added. After that addition, all five vertices have degree \(4\), the maximum possible in a simple graph on five vertices. Thus the closure is \(K_5\).
Check: the original edge set has \(8\) edges, and the two additions give \(8+2=10\) edges. A complete simple graph on five vertices has \(\binom{5}{2}=5\cdot4/2=10\) edges, as required. The original graph is Hamiltonian: \(1,4,2,3,5,1\) uses edges \(14,24,23,35,15\), all of which are in the original edge set. The closure theorem also certifies Hamiltonicity from the complete closure.
A Longer Sequence and a Hamiltonian Cycle
Worked Example: A Six-Vertex Graph Whose Closure Is Complete
Let \(G\) have vertex set \(\{1,2,3,4,5,6\}\) and edge set consisting of every pair from this vertex set except \(12,23,34,45\). Thus the listed four pairs are exactly the nonedges. Counting the incident edges gives degrees \((4,3,3,3,4,5)\): vertices \(1\) and \(5\) each miss one neighbor, vertices \(2,3,4\) each miss two, and vertex \(6\) misses none.
Here \(n=6\). The initial eligibility calculations are \(d(1)+d(2)=4+3=7\) for \(12\), \(d(2)+d(3)=3+3=6\) for \(23\), \(d(3)+d(4)=3+3=6\) for \(34\), and \(d(4)+d(5)=3+4=7\) for \(45\). All four nonedges meet the threshold. Add them in the order shown below, recomputing the degrees after each addition.
| Step | Degrees after the step | Next edge calculation |
|---|---|---|
| Start | \((4,3,3,3,4,5)\) | Add \(23\): \(3+3=6\) |
| Add \(23\) | \((4,4,4,3,4,5)\) | Add \(12\): \(4+4=8\) |
| Add \(12\) | \((5,5,4,3,4,5)\) | Add \(34\): \(4+3=7\) |
| Add \(34\) | \((5,5,5,4,4,5)\) | Add \(45\): \(4+4=8\) |
| Add \(45\) | \((5,5,5,5,5,5)\) | No nonedges remain |
At every row the degrees are those of the graph after the additions in that row. The final degrees are all \(5\), so every vertex is adjacent to all five other vertices and the closure is \(K_6\). By the closure theorem, the original graph is Hamiltonian.
Check: the original graph has \(\binom{6}{2}-4=15-4=11\) edges. The four closure additions give \(11+4=15\), the number of edges in \(K_6\). A Hamiltonian cycle can also be checked directly in the original graph: \(1,3,5,2,4,6,1\). Its six edges are \(13,35,25,24,46,16\); none is one of the four omitted pairs \(12,23,34,45\). Thus every edge of this cycle was already present.
When the Closure Does Not Become Complete
If the process stops with missing edges, the closure theorem has not established that the original graph is non-Hamiltonian. It only says that the original graph and the terminal graph have the same Hamiltonicity status. The terminal graph might be Hamiltonian without being complete; alternatively, it might not be Hamiltonian. The next examples distinguish these possibilities.
Worked Example: A Hamiltonian Graph with No Closure Additions
Let \(G\) have \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,23,34,45,15\}\), the cycle \(C_5\). Each vertex is incident with exactly two listed edges, so every degree is \(2\). The nonedges are \(13,14,24,25,35\). For each of them, the degree sum is \(2+2=4\), which is less than \(n=5\). Therefore the closure process adds no edges and stops at \(C_5\), not at a complete graph.
Check: the cycle \(1,2,3,4,5,1\) uses exactly the five listed edges and visits every vertex once before returning to \(1\). Hence \(G\) is Hamiltonian even though its closure is not complete. Failure to reach a complete graph means this particular certificate does not apply; it does not mean the graph has no Hamiltonian cycle.
Worked Example: An Incomplete Closure for a Non-Hamiltonian Graph
Let \(G\) have \(V(G)=\{c,1,2,3,4\}\) and \(E(G)=\{c1,c2,c3,c4\}\), the star \(K_{1,4}\). The center \(c\) has degree \(4\), and each leaf has degree \(1\). The only nonedges are pairs of leaves; for any such pair \(i,j\), the degree sum is \(1+1=2<5\). No edge is added, so the closure is the same star.
Check: a vertex on a Hamiltonian cycle has two distinct incident cycle edges. Each leaf here has only one incident edge in the graph, so no Hamiltonian cycle can include that leaf. Thus the graph is non-Hamiltonian, but this conclusion comes from the degree obstruction, not merely from its unchanged closure.
Why the Computation Works—and Common Errors
The closure procedure is reliable because each permitted addition preserves Hamiltonicity in both directions. More explicitly, suppose the successive graphs are \(G_0,G_1,\ldots,G_r\), where \(G_0\) is the input graph and \(G_{i+1}\) is obtained by adding one eligible edge to \(G_i\). The closure theorem gives “\(G_i\) is Hamiltonian if and only if \(G_{i+1}\) is Hamiltonian” for each \(i\). Chaining these equivalences gives that \(G_0\) is Hamiltonian if and only if \(G_r\) is Hamiltonian. If \(G_r=K_n\) with \(n\ge3\), the cycle through the vertices in any order is a Hamiltonian cycle in \(G_r\), so \(G_r\) is Hamiltonian and therefore \(G_0\) is Hamiltonian.
A common computational error is to use the original degrees at every step. In the five-vertex example, after adding \(12\), the degree of vertex \(1\) is \(3\), not \(2\). The remaining pair \(13\) must therefore be tested using \(3+3=6\), not the original sum \(2+3=5\). The original sum happens to meet the threshold in that example, but in other calculations an update can change an initially ineligible pair into an eligible one.
Another error is to treat a missing edge in the final closure as evidence against Hamiltonicity. The \(C_5\) example has no eligible additions, yet its defining cycle is Hamiltonian. Use the complete-closure conclusion only when the terminal graph really is complete. Otherwise, the closure computation alone is inconclusive; inspect the terminal graph or use another valid argument.
Write down its order, its present edges or nonedges, and its current degrees.
For nonadjacent \(u,v\), calculate \(\deg(u)+\deg(v)\) in the current graph and compare it with \(n\).
If the sum is at least \(n\), add \(uv\) and increase the degrees of \(u\) and \(v\) by \(1\).
Stop only when no nonedge meets the condition. A complete terminal graph certifies Hamiltonicity; an incomplete one does not decide it by itself.
Check Your Understanding
For each calculation, use degrees in the graph at the stated stage, not degrees from an earlier stage.
- On six vertices, a current nonedge joins vertices of degrees \(2\) and \(4\). Is it eligible for addition? What changes after it is added?
- For the graph on \(\{1,2,3,4\}\) with edge set \(\{12,23,34,41\}\), calculate the closure and state whether it is complete.
- Why does a complete closure on at least three vertices imply that the original graph is Hamiltonian?
- A closure computation stops at an incomplete graph. What conclusion about Hamiltonicity is justified by the closure theorem alone?
- In a closure calculation, explain why a degree sum that was below \(n\) may need to be tested again after other edges have been added.