The Degree-Sum Rule
A graph can be transformed by adding edges that are absent but whose endpoints already have sufficiently large degrees. The threshold is the order of the graph: for a graph on \(n\) vertices, an absent edge \(uv\) qualifies when \(d(u)+d(v)\ge n\). Repeating this operation gives the Bondy–Chvátal closure. The calculation requires care because every added edge increases the degrees of both its endpoints, and those increases can make further nonedges qualify.
Throughout, graphs are finite and simple. A nonedge is an unordered pair of distinct vertices that is not in the edge set. Adding an edge does not change the vertex set or the order \(n=|V|\). In particular, degrees are recalculated in the current graph at every step, while the threshold \(n\) stays fixed.
A sequence may add one qualifying edge at a time, or may add several edges that qualify in the current graph at once. The degrees used to decide which edges qualify must be those before that round of additions. After the round, recalculate degrees before deciding on the next round. We will prove that the process terminates and that every valid choice of additions gives the same final graph.
Why the Process Has a Unique Outcome
Proof. Each operation adds one edge, never removes an edge, and preserves the vertex set. There are at most \(\binom{n}{2}\) possible edges on \(n\) vertices, so only finitely many additions can occur. A process that continues whenever a qualifying nonedge exists must therefore stop at a graph with no such nonedge.
To prove uniqueness, take any two terminal graphs \(C_1\) and \(C_2\) obtained from \(G\) by valid sequences. We first show that every edge added in the sequence producing \(C_1\) also belongs to \(C_2\). The original edges of \(G\) belong to \(C_2\). Suppose inductively that all edges present just before an addition in the \(C_1\) sequence belong to \(C_2\), and that the next edge added is \(uv\). Degrees cannot decrease when edges are added, so \(d_{C_2}(u)\) and \(d_{C_2}(v)\) are at least their degrees just before this addition. Thus \(d_{C_2}(u)+d_{C_2}(v)\ge n\). If \(uv\) were absent from \(C_2\), it would be a qualifying nonedge there, contrary to \(C_2\) being terminal. Hence \(uv\) belongs to \(C_2\). Induction over the sequence gives \(E(C_1)\subseteq E(C_2)\). Interchanging \(C_1\) and \(C_2\) gives \(E(C_2)\subseteq E(C_1)\), so their edge sets, and therefore the graphs, are equal. \(\square\)
This proof also explains a useful stopping test: a graph is the closure exactly when every nonedge \(uv\) satisfies \(d(u)+d(v)<n\). If there are no nonedges, the condition holds automatically. For an order-zero or order-one graph there are no pairs of distinct vertices, so the process stops immediately.
Computing a Closure
Worked Example: One Addition and a Complete Check
Let \(G\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,14,25,35\}\). Its order is \(n=5\). Find its closure.
Count the neighbors of each vertex from the stated edge set: vertex \(1\) is incident with \(12,13,14\), vertex \(2\) with \(12,25\), vertex \(3\) with \(13,35\), vertex \(4\) with \(14\), and vertex \(5\) with \(25,35\). Thus the degrees are \(3,2,2,1,2\), respectively. Listing all absent pairs gives \(15,23,24,34,45\). Their degree sums, in that order, are \(3+2=5\), \(2+2=4\), \(2+1=3\), \(2+1=3\), and \(1+2=3\). Only \(15\) qualifies, since the rule is “at least \(5\).”
Add \(15\). The new edge set is \(\{12,13,14,15,25,35\}\), and the degrees are now \(4,2,2,1,3\): the degrees of \(1\) and \(5\) each increased by \(1\), and the others stayed the same. The remaining nonedges are \(23,24,34,45\). Their degree sums are \(2+2=4\), \(2+1=3\), \(2+1=3\), and \(1+3=4\), all less than \(5\).
Check: the original graph has \(5\) edges and exactly one edge was added, so the final graph has \(6\) edges. There are \(\binom{5}{2}=10\) possible pairs, leaving \(10-6=4\) nonedges, exactly \(23,24,34,45\). None qualifies, so the final edge set is the closure.
Worked Example: Additions That Trigger Further Additions
Let \(G\) have \(V=\{u,v,w,a,b,c\}\) and \(E=\{ua,ub,uc,vw,va,vb,wc\}\). Here \(n=6\), so a nonedge qualifies when the endpoint degrees sum to at least \(6\). The degrees read from the edge set are \(d(u)=3\), \(d(v)=3\), \(d(w)=2\), \(d(a)=2\), \(d(b)=2\), and \(d(c)=2\).
Initially \(uv\) is a nonedge with degree sum \(3+3=6\), so add it. Every other nonedge initially has degree sum at most \(3+2=5\) or \(2+2=4\), and does not qualify. After adding \(uv\), the degrees of \(u\) and \(v\) each rise by \(1\): they are now \(4,4,2,2,2,2\) in the order \(u,v,w,a,b,c\). The nonedges \(uw\) and \(vc\) now qualify, since \(4+2=6\) for each. Add \(uw\) first.
After adding \(uw\), the degrees in that same vertex order are \(5,4,3,2,2,2\). The pair \(vc\) is still a nonedge, and its sum is \(4+2=6\), so add \(vc\). The resulting graph has edge set \(\{ua,ub,uc,vw,va,vb,wc,uv,uw,vc\}\), with degrees \(5,5,3,2,2,3\). The remaining nonedges are \(wa,wb,ab,ac,bc\). Their degree sums are \(3+2=5\), \(3+2=5\), \(2+2=4\), \(2+3=5\), and \(2+3=5\), respectively. Thus none qualifies.
Check: the displayed final edge set has \(10\) edges, and the degree sum is \(5+5+3+2+2+3=20=2\cdot10\). There are \(\binom{6}{2}=15\) possible pairs, so there must be \(15-10=5\) nonedges; the five listed above account for all of them. The graph is terminal and hence is the closure.
Worked Example: Closing a Four-Cycle
Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\). Each vertex has degree \(2\), and \(n=4\). The only nonedges are \(13\) and \(24\). Each has endpoint degree sum \(2+2=4\), so both qualify. Add them; the resulting edge set is \(\{12,23,34,41,13,24\}\).
Every pair of distinct vertices is now an edge: the six pairs are \(12,13,14,23,24,34\). The final graph is \(K_4\), with each vertex of degree \(3\), and it has no nonedges left to test.
Check: the starting graph had \(4\) edges, and the two diagonals were added, giving \(4+2=6\) edges. Also, \(\binom{4}{2}=6\), so six edges account for every possible pair. This confirms that the result is complete and terminal.
How to Organize the Calculation
For a larger graph, a systematic record helps avoid overlooking a pair or using stale degrees. At each stage, record the current degrees, list all current nonedges, and test each sum against the fixed threshold \(n\). Once an edge is added, update both endpoint degrees before testing the next stage. The following procedure describes the calculation; its termination and independence from choices follow from the proposition above.
Count the vertices once and set \(n=|V|\). This number does not change during closure.
For each absent pair \(uv\), compute the current sum \(d(u)+d(v)\). A pair qualifies if and only if this sum is at least \(n\).
Add a qualifying edge and increase the degrees of its two endpoints by \(1\). Repeat the test using these updated degrees.
When no nonedge qualifies, check that all remaining nonedges have degree sum less than \(n\). The resulting graph is the closure.
If several nonedges qualify at the same stage, they may be added in any order. They may also be added together as one round, provided the tests for that round use the degrees before any edge in the round is added. Subsequent tests use the updated degrees. The uniqueness proof ensures that either approach reaches the same closure.
Common Pitfalls and the Role of Closure
Omitting a nonedge from the final check. In the first example, after adding \(15\), the nonedge \(23\) must still be listed: it is absent from the stated edge set. Its sum is \(d(2)+d(3)=2+2=4<5\), so it does not qualify, but omitting it would make the terminal check incomplete. A reliable check counts all pairs: on five vertices there are \(\binom{5}{2}=10\) pairs, and the six final edges in that example leave exactly four nonedges.
Updating only one endpoint. When an edge \(uv\) is added, both \(d(u)\) and \(d(v)\) increase by \(1\). For instance, in the second example, adding \(uv\) changes the degrees \(d(u)=3,d(v)=3\) to \(d(u)=4,d(v)=4\). Keeping either degree at \(3\) would give an incorrect test for later nonedges.
Changing the threshold. The condition compares a degree sum with the order \(n\), not with the number of edges, the maximum degree, or a threshold recalculated after an addition. In the second example, the threshold remains \(6\) throughout all three additions.
The closure packages a sequence of local degree-sum tests into a single graph associated with \(G\). The Ore degree-sum criterion, covered in the earlier material, is a useful special situation where degree sums are tested for nonadjacent pairs. Closure repeatedly applies that same threshold rule while degrees change. The calculation itself establishes the resulting graph; conclusions relating closure to Hamiltonian cycles require a separate theorem.
Check Your Understanding
For each question, use degrees in the graph at the stated stage and compare with its fixed order.
- In the graph on \(\{1,2,3,4\}\) with edge set \(\{12,23\}\), which nonedges qualify for addition at the first step?
- Explain why adding one edge cannot make the degree of any vertex decrease.
- For the graph in the first worked example, verify the degree sum of every remaining nonedge after \(15\) is added.
- Why does finiteness of the possible edge set guarantee that repeated valid additions cannot continue forever?
- State the condition that must hold for a graph to be terminal in the closure process.