The Closure Theorem for Hamiltonian Graphs

The Single-Edge Closure Theorem

A graph may fail to contain a particular edge while having its endpoints connected to many other vertices. The degree-sum condition in the closure theorem says that if those two endpoints together have enough neighbors, adding the missing edge cannot change whether the graph is Hamiltonian. The key point is the reverse direction: if a Hamiltonian cycle uses the new edge, the other edges of that cycle give a spanning path, and the degree condition lets us close that path by using two edges already in the graph.

All graphs in this tutorial are finite and simple. A Hamiltonian cycle is a cycle that visits every vertex of the graph exactly once before returning to its starting vertex. A graph is Hamiltonian if it contains such a cycle. A Hamiltonian path is a path that visits every vertex exactly once; unlike a Hamiltonian cycle, its two endpoints need not be adjacent.

Definition: If \(u\) and \(v\) are distinct nonadjacent vertices of \(G\), then \(G+uv\) is the graph with the same vertex set as \(G\) and edge set \(E(G)\cup\{uv\}\). The edge \(uv\) is a nonedge of \(G\).

In the theorem below, the degrees are measured in \(G\), before \(uv\) is added. This matters: adding the edge increases each endpoint’s degree by one, but the hypothesis is about the original degrees.

Theorem (Bondy–Chvátal, single-edge form): Let \(G\) be a simple graph of order \(n\ge 3\), and let \(u,v\) be nonadjacent vertices of \(G\). If \(\deg_G(u)+\deg_G(v)\ge n\), then \(G\) is Hamiltonian if and only if \(G+uv\) is Hamiltonian.

Why the Reverse Direction Holds

If \(G\) is Hamiltonian, the same Hamiltonian cycle is present in \(G+uv\), since adding an edge does not remove any edges. To prove the other direction, suppose \(G+uv\) has a Hamiltonian cycle. If that cycle does not use \(uv\), it is already a Hamiltonian cycle in \(G\). It remains to consider a cycle that does use the newly added edge.

Removing \(uv\) from that cycle leaves a Hamiltonian path in \(G\), with endpoints \(u\) and \(v\). Write its vertices in order as \(x_1,x_2,\ldots,x_n\), where \(x_1=u\) and \(x_n=v\). Thus each consecutive pair \(x_ix_{i+1}\) is an edge of \(G\), and the path includes every vertex exactly once.

Consider the \(n-1\) possible positions between consecutive vertices of this path. Let \(A\) be the set of positions \(i\) for which \(u\) is adjacent in \(G\) to \(x_{i+1}\). Let \(B\) be the set of positions \(i\) for which \(v\) is adjacent in \(G\) to \(x_i\). Each neighbor of \(u\) appears exactly once among \(x_2,\ldots,x_n\); because \(uv\) is absent, none is \(x_n=v\). Therefore \(|A|=\deg_G(u)\). Similarly, each neighbor of \(v\) appears exactly once among \(x_1,\ldots,x_{n-1}\), and none is \(x_1=u\), so \(|B|=\deg_G(v)\).

Both \(A\) and \(B\) are subsets of the same set of \(n-1\) positions. Since \(|A|+|B|\ge n\), they cannot be disjoint: if they were disjoint, their union would have at least \(n\) elements despite containing at most \(n-1\). Choose a position \(i\) in \(A\cap B\). Then \(ux_{i+1}\) and \(vx_i\) are edges of \(G\).

Combining those two edges with the path edges gives the cycle

u=x_1,\ x_{i+1},x_{i+2},\ldots,x_n=v,\ x_i,x_{i-1},\ldots,x_1=u.

The displayed order uses every vertex exactly once before returning to \(u\). Each consecutive pair is an edge of \(G\): the first and the turn from \(v\) to \(x_i\) use the two edges given by \(i\in A\cap B\), and all other edges are path edges. Also, \(i\) cannot be \(1\), since \(vx_1=vu\) is absent, and cannot be \(n-1\), since \(ux_n=uv\) is absent. Thus the two added connections do not collapse the displayed cycle at an endpoint. We have constructed a Hamiltonian cycle in \(G\), completing the reverse direction. \(\square\)

Worked Applications

Worked Example: Recovering a Cycle from a Spanning Path

Let \(G\) have vertex set \(V=\{1,2,3,4,5,6\}\) and edge set \(E=\{12,23,34,45,56,13,14,26,36\}\). Consider the nonedge \(16\).

The neighbors of \(1\) are \(2,3,4\), so \(\deg_G(1)=3\). The neighbors of \(6\) are \(2,3,5\), so \(\deg_G(6)=3\). Thus the degree sum is \(3+3=6\), equal to the order \(n=6\). The theorem applies.

In \(G+16\), the cycle \(1,6,5,4,3,2,1\) uses the new edge \(16\). Removing that edge leaves the spanning path \(1,2,3,4,5,6\). To carry out the counting argument, set \(x_1=1,\ldots,x_6=6\). For \(A\), test the possible edges from \(1\) to \(x_2,\ldots,x_6\): the edges \(12,13,14\) give positions \(1,2,3\), while \(15,16\) are absent in \(G\). Hence \(A=\{1,2,3\}\). For \(B\), test edges from \(6\) to \(x_1,\ldots,x_5\): the edges \(62,63,65\) give positions \(2,3,5\), while \(61,64\) are absent. Hence \(B=\{2,3,5\}\).

The intersection is \(A\cap B=\{2,3\}\). Choosing \(i=2\) gives the cycle \(1,3,4,5,6,2,1\). Its edges are \(13,34,45,56,62,21\), all in \(G\), and it visits all six vertices exactly once.

Check: the new-edge cycle in \(G+16\) uses \(16,65,54,43,32,21\); the recovered cycle in \(G\) uses \(13,34,45,56,62,21\). Each list contains six edges and returns to its starting vertex, verifying both cycles directly.

Worked Example: The Condition Does Not Guarantee Hamiltonicity

Let \(G\) have vertex set \(V=\{a,b,x,y,z\}\) and edge set \(E=\{ax,ay,az,bx,by,bz\}\). This is \(K_{2,3}\), with parts \(\{a,b\}\) and \(\{x,y,z\}\). The pair \(a,b\) is a nonedge. Each is adjacent to \(x,y,z\), so \(\deg_G(a)=3\), \(\deg_G(b)=3\), and their sum \(3+3=6\) is at least \(n=5\).

The theorem says that \(G\) and \(G+ab\) have the same Hamiltonicity status; it does not say that either graph must be Hamiltonian. In \(G+ab\), each of \(x,y,z\) has exactly two neighbors, namely \(a\) and \(b\). If a Hamiltonian cycle existed, it would have to use both incident edges at each of \(x,y,z\), because every vertex on a cycle has two incident cycle edges. It would therefore use \(ax,ay,az\), giving \(a\) three incident edges in the cycle. That is impossible, since a cycle uses exactly two edges at each of its vertices.

So \(G+ab\) is not Hamiltonian. Nor is \(G\): any Hamiltonian cycle in \(G\) would also be a Hamiltonian cycle in the larger graph \(G+ab\), which we have ruled out. This agrees with the theorem: the edge addition preserves the answer, but the degree-sum hypothesis alone is not a Hamiltonicity test.

Check: the order is \(5\), while the original endpoint degree sum is \(3+3=6\). The argument rules out a cycle in the augmented graph by counting the three forced edges at \(a\); the original graph is ruled out because it is a subgraph of the augmented graph.

Worked Example: What Can Happen Below the Threshold

Let \(G\) have vertex set \(V=\{1,2,3,4,5\}\) and edge set \(E=\{12,23,34,45\}\), so \(G\) is the path \(P_5\). The endpoints \(1\) and \(5\) are nonadjacent. Their degrees in \(G\) are both \(1\), so the sum is \(1+1=2\), which is less than \(n=5\).

Adding the edge \(15\) gives the cycle \(1,2,3,4,5,1\), which is Hamiltonian. The original graph is not Hamiltonian: vertices \(1\) and \(5\) each have degree \(1\), whereas a vertex on a cycle must have two incident cycle edges. Thus the Hamiltonicity status changes when the degree-sum hypothesis fails.

Check: the augmented cycle uses the five edges \(12,23,34,45,15\), visits all five vertices once, and returns to \(1\). In the original graph the endpoint degrees remain \(1\) and \(1\), so neither endpoint can lie on a cycle.

Using the Theorem Correctly

The theorem gives an equivalence for a particular nonedge satisfying a particular condition. It does not assert that a graph is Hamiltonian whenever a pair of vertices has degree sum at least the order. Its practical conclusion is narrower: for that pair, adding the edge leaves the yes-or-no answer to the Hamiltonicity question unchanged. The edge may help make a Hamiltonian cycle visible, but if the augmented graph has no such cycle, the original graph cannot have one either.

Common mistake: treating the degree-sum condition as a sufficient condition for Hamiltonicity. In the \(K_{2,3}\) example, the original degrees of \(a,b\) sum to \(6\), which is at least the order \(5\). It would be wrong to conclude from \(6\ge5\) that \(G+ab\) is Hamiltonian. The theorem instead says \(G\) is Hamiltonian if and only if \(G+ab\) is Hamiltonian; the forced-edge argument shows both are non-Hamiltonian.

A second error is to calculate the endpoint degrees after adding the edge and then use those numbers in the hypothesis. The condition is \(\deg_G(u)+\deg_G(v)\ge n\), not a condition on the degrees in \(G+uv\). The added edge itself is reserved for the forward implication; the reverse implication must construct its cycle using edges already present in \(G\).

The counting step explains the threshold. The spanning path has \(n-1\) positions, while the two endpoint neighborhoods supply at least \(n\) incidences with those positions. At least one position is therefore counted from both ends. At that position, the two existing edges reconnect the path into a spanning cycle. This is why the condition involves the sum of the two degrees, rather than a requirement on either degree separately.

Check Your Understanding

For each question, use degrees in the graph before any edge is added.

In a graph of order \(8\), a nonadjacent pair has degrees \(3\) and \(5\). Does the single-edge closure theorem apply? What does it conclude?
Explain why a Hamiltonian cycle in \(G+uv\) that avoids \(uv\) is already a Hamiltonian cycle in \(G\).
In the reverse-direction proof, why are the sets of positions \(A\) and \(B\) both subsets of a set with \(n-1\) elements?
For the graph \(K_{2,3}\), explain why each of \(x,y,z\) would force two cycle edges if a Hamiltonian cycle existed in \(G+ab\).
Give a graph and nonedge for which adding the edge changes Hamiltonicity, and explain why this does not contradict the theorem.