Motivation
A missing edge may make a Hamiltonian cycle easier to see without actually changing whether one exists. If its endpoints already have sufficiently large total degree, a cycle using the added edge can be repaired into a cycle using only old edges. Repeating that safe operation produces a closure graph.
The closure also explains a less obvious sufficient condition expressed through the sorted degree sequence. A closed noncomplete graph must expose a pair of degree shortages at complementary positions. If the original sequence forbids every such shortage, the closure is complete and the graph is Hamiltonian.
The criteria below are sufficient certificates; neither incomplete closure nor failure of a degree test is treated as a complete non-Hamiltonicity decision.
Definitions
Definition 4.2.1
(Safe edge additions and closure)
Let be a finite simple undirected graph on vertices. A Hamiltonian cycle visits every vertex exactly once before returning to its start. For a nonadjacent pair , an eligible closure addition joins them when their current degrees satisfy .
Repeat eligible additions until none remains. A graph at that stopping point is closed: every remaining nonedge has endpoint degree sum at most . Degrees and eligibility are recomputed in the evolving graph, not frozen at their initial values.
Definition 4.2.2
(Degree-sequence condition)
Write the original degrees in nondecreasing order . The degree-sequence condition in this note is that, for every integer with ,
The two alternatives belong to the same index test; requiring both would be a stronger condition than the theorem uses. The sequence records only degrees, not which vertices have them.
Theorem/Proposition
Lemma 4.2.3
(An eligible edge preserves Hamiltonicity in both directions)
If are nonadjacent and , then is Hamiltonian if and only if is Hamiltonian. A Hamiltonian cycle using the new edge can be converted explicitly to one in by two cross-edges along the resulting spanning path.
Theorem 4.2.4
(Closure is independent of the addition order)
All maximal sequences of eligible additions give the same final graph, the closure of . The graph and its closure are Hamiltonian together. In particular a complete closure proves Hamiltonicity and permits recovery of a cycle in the original graph.
A straightforward adjacency-matrix construction takes elementary operations; a stored addition history permits cycle recovery in additional work once a closure cycle is supplied. These are elementary bounds, not fastest implementation claims.
Theorem 4.2.5
(The degree-sequence condition guarantees a Hamiltonian cycle)
Every finite simple graph of order at least three satisfying the displayed sorted-degree condition is Hamiltonian. The condition is monotone under edge addition, and it forces its closure to be complete.
As a corollary, minimum degree at least implies Hamiltonicity, since it makes the first alternative hold at every required index. Failure of the degree-sequence condition need not imply failure of Hamiltonicity.
Concept lensStructural
Closure strengthens a representation while preserving one yes-or-no property
Safe additions may change many graph features, but preserve Hamiltonicity. The degree sequence supplies a monotone sufficient test forcing that strengthened representation to become complete. A positive closure certificate transfers back through local repairs; a negative outcome has no comparable general transfer to non-Hamiltonicity.
Proof sketch or proof idea
Proof
(Two cross-edges close the spanning path)
One implication of the edge-addition lemma is immediate: an old Hamiltonian cycle remains in the enlarged graph. For the converse take a cycle in . If it avoids the added edge, no repair is needed. Otherwise remove that edge to obtain a spanning path
whose edges all belong to .
In the index set , let consist of indices for which is adjacent to , and of indices for which is adjacent to . Their sizes are and : the path lists all vertices, and the missing edge excludes the opposite endpoint from either neighbor list.
Their total size is at least , exceeding the available indices, so some index belongs to both. It cannot be one or , because that would require the missing edge. The sequence
is therefore a Hamiltonian cycle in . Its two cross-edges come from the intersection, and every other edge is part of the spanning path. All vertices occur exactly once before the return. This proves the local equivalence constructively.
Proof X-ray
Neighbor index sets must overlap on the spanning path
The degree hypothesis is used only after the added edge has been removed from the cycle. What remains is a spanning path whose edges lie in , and only along such a path can neighbors be turned into indices. The key move is the offset: a neighbor of is recorded at index , a neighbor of at index . A common index then delivers the two cross-edges and at once, and reversing the segment closes the cycle.
The pigeonhole count is where the threshold enters. Nonadjacency of and is used to rule out the shared index being or , either of which would need the missing edge. The threshold cannot be lowered to : in the path the endpoints have degree sum , adding gives a triangle, but the path itself has no Hamiltonian cycle.
Why the final closure does not depend on choices
Proof
(Every closed supergraph contains every eligible addition)
Each addition increases degrees and there are only finitely many missing edges, so every eligible-addition sequence terminates. Every step preserves Hamiltonicity by the lemma.
Let be any closed graph on the same vertex set that contains every original edge. Every edge added in any eligible sequence must belong to . Prove this by induction through that sequence. Earlier added edges belong to by induction, so the degrees in are at least those when the next edge was eligible. If that next edge were absent from , its endpoint sum in would still be at least , contradicting closedness.
Apply this statement with equal to the final graph of another sequence. Each final closure is contained in the other, proving equality. This also proves closure is a well-defined graph operation rather than just one arbitrary execution.
Maintain degrees and an adjacency matrix. A full scan of at most pairs finds one eligible nonedge or certifies that none remains. Add it, update its two degrees and repeat. There are at most additions, giving total work including the final scan. The matrix uses storage and the addition history has the same order of size.
If the closure is complete, start with any cyclic ordering of its vertices. Process the additions backward. At each step delete the recorded edge from the current graph. If the current cycle avoids it, keep the cycle. Otherwise apply the lemma's path repair using the graph just before that edge was added. All later additions have already been removed, so the repair uses only currently legitimate edges. Checking and rebuilding a cycle and its crossing index takes work with matrix lookups, giving over the whole history.
A closed noncomplete graph exposes a forbidden degree pattern
Proof
(A maximum-sum nonedge violates both alternatives)
First, the sorted-degree condition is preserved when edges are added. Every individual vertex degree increases or stays the same, and therefore every sorted order statistic also does. For example, if the new th-smallest degree were smaller than the old one, at least vertices would have new degrees below that old threshold, although none decreased; this contradicts the old ordering. Each disjunction in the condition consequently remains true.
Assume the closure is not complete. If it has an isolated vertex, every degree is at most . At index one the first alternative fails, and the required degree also fails. Thus a graph satisfying the condition cannot have this case.
Otherwise choose a nonadjacent pair with maximum possible degree sum, labeling it so that . There are no isolated vertices, so . Closedness gives and hence .
Every non-neighbor of , other than itself, has degree at most . A larger degree would create a nonedge with a larger sum than the chosen pair. There are such vertices. Therefore the th-smallest degree in is at most .
Likewise every non-neighbor of has degree at most . There are such vertices; include itself, whose degree is also at most . We have at least vertices with degrees at most , so the th-smallest degree is less than .
Both alternatives of the degree test fail at the permitted index . This contradicts preservation of the original condition under closure. The closure must therefore be complete, and the local-equivalence theorem yields a Hamiltonian cycle in the original graph.
The minimum-degree corollary now follows directly: if every degree is at least , then for each even the th-smallest degree is greater than . This recovers that sufficient condition through the stronger sorted-sequence argument, without using it as an unproved premise.
Proof X-ray
Why the contradiction is sought in the closure
The proof never searches the original graph for a bad index. It first shows that the condition survives every edge addition, so it still holds in the closure , where closedness is available. The real idea is the choice of a nonedge of maximum degree sum: maximality turns non-neighbors into degree bounds, at most for non-neighbors of and at most for non-neighbors of .
Closedness, , does double duty. It supplies at least non-neighbors of , and together with it gives , so is an index the condition actually tests. The isolated-vertex case is split off only to guarantee .
Worked examples
Worked example 4.2.6
(Closure can succeed when the initial nonedge sum test fails)
Take a five-vertex clique on , delete edge , and add a sixth vertex adjacent only to . The sorted degrees are . The nonedge initially has degree sum five, below the order six, so a condition demanding the bound for every original nonedge fails.
Nevertheless is eligible, since its sum is six. After adding it, has degree three, so and can be added; finally is eligible too. The closure is complete. The degree-sequence test also succeeds: its only indices are one and two, and the corresponding degrees exceed those indices. One original Hamiltonian cycle is .
Worked example 4.2.7
(An isolated vertex has an explicit early sequence failure)
Take a clique on five vertices and one isolated vertex, for total order six. Its sequence is . At index one, the first alternative fails because zero is not greater than one, and the second fails because the fifth degree is four rather than at least five.
Every nonedge joins the isolated vertex to a degree-four vertex, so none is eligible. The closure remains incomplete, and the graph is not Hamiltonian because the isolated vertex cannot lie on a spanning cycle. Here both negative tests agree with a separate direct obstruction; that agreement is not a general converse theorem.
Worked example 4.2.8
(Repair one specific added edge back into the original graph)
In the first graph, add only . The enlarged graph has cycle , which uses that new edge. Removing it gives the spanning path , with endpoints and the other endpoint in the lemma's notation.
Along that indexed path, the first endpoint's neighbor-index set is and the last endpoint's is . Their shared index three gives the repaired cycle . Every listed edge belongs to the original graph; the added edge has disappeared.
For a longer addition history, apply this same repair backward one edge at a time. The maintained cycle always belongs to the current graph, so the final output uses only original edges rather than treating closure edges as if they had always existed.
Common mistakes
Counterexample mode
A noncomplete closure can already be Hamiltonian
A five-cycle has degree two at every vertex. Every nonedge has sum four, below five, so its closure is unchanged and noncomplete. Yet the graph itself is a Hamiltonian cycle. Its degree-sequence test fails at index two as well: the second degree is not greater than two, and the third is below three. Both tests are sufficient, not necessary.
Common mistake
(Freezing the initial degrees)
Use current degrees when testing additions. In the first worked example, fails the test at the start, with sum five, and becomes eligible only after has raised to three.
Common mistake
(Turning the disjunction into a requirement)
Do not interchange the degree-sequence alternatives with an unconditional requirement on the larger-index degree. Under minimum degree at least , the first alternative holds at every index, and nothing at all is required of .
Common mistake
(Repairing along a path that is not spanning)
A spanning path created by removing an added cycle edge is essential to the repair; an arbitrary graph path need not include all vertices, and closing it gives a cycle that misses some of them.
Summary
A large endpoint degree sum makes adding a missing edge safe for Hamiltonicity. Repeated additions give an order-independent closure with constructive cycle recovery. A maximum-sum nonedge in any closed noncomplete graph forces a forbidden sorted-degree pattern, proving the full degree-sequence condition and explaining the limits of failed tests.
Exercises
Quick check
(Show directly that minimum degree at least makes every index test in the degree-sequence condition succeed.)
The required indices are strictly smaller than .
Solution · Answer
Every sorted degree is at least the minimum degree and hence at least . For every permitted integer , this makes . Thus the first alternative holds and the second need not be checked. The degree-sequence theorem proves Hamiltonicity under this hypothesis.
Quick check
(Why does adding other eligible edges never make a previously eligible missing edge ineligible? Does this alone prove that every stopping graph is the same?)
Use monotone degrees for the first question and closed-supergraph containment for the second.
Solution · Answer
Adding edges cannot decrease either endpoint degree, so an eligible edge remains eligible until it is added. To prove uniqueness of the stopping graph, compare with any closed supergraph containing the original graph. Inductively it must contain every edge in an eligible sequence, since otherwise its endpoint degrees would contradict closedness. Taking two stopping graphs as the comparison supergraphs proves mutual containment. Monotonicity supplies the degree comparison; closedness supplies the contradiction.
Quick check
(In the maximum-sum nonedge proof, explain separately why at least degrees are at most and why at least degrees are at most .)
Count non-neighbors of the two different chosen vertices; include itself only in the second count.
Solution
The vertex has at least non-neighbors because . Every one has degree at most , or its pair with would exceed the chosen maximum sum. This gives the first order-statistic bound.
The vertex has non-neighbors, each of degree at most by the same maximality. Add itself, whose degree is no larger than because . This gives qualifying vertices and the second order-statistic bound. Together they violate both alternatives at index .