Part III · The Deep Theory

Hamilton Cycles

Created by Felipe Casadei

A Hamilton cycle is a round trip that visits every vertex exactly once. After this chapter you will know why no clean test for one is expected to exist, and you will own the classic toolbox that guarantees one anyway: Dirac's degree bound, Chvátal's complete answer for degree sequences, and Fleischner's theorem on squared graphs.

The other grand tour

Picture a road network: towns as vertices, roads as edges. Two natural "grand tour" questions come up. Can you take a round trip that drives along every road exactly once? And can you take a round trip that visits every town exactly once? The two questions sound like twins. They are not.

The first question, about edges, was settled back in Chapter 1. A closed walk that uses every edge exactly once is an Euler tour, and a connected graph has one exactly when every vertex has even degree^[4]. That is a complete answer. You can check it by glancing at each vertex and counting.

The second question, about vertices, is this chapter's subject, and it has no such answer. Nobody knows a clean test, and there are strong reasons to believe none exists.

The name honours W. R. Hamilton, who in 1857 sold a puzzle game asking players to find exactly such tours on the graph of the dodecahedron, the twelve-sided die shape^[5]. Figure 10.1 shows the graph and one winning tour. The same family of puzzles is much older than graph theory: asking whether a knight can visit every square of a chessboard exactly once and hop back to its start is a Hamilton cycle question in disguise. So is the puzzle of listing all the on/off settings of a row of switches so that each step flips just one switch: that is a Hamilton cycle in the cube-like graph whose vertices are the settings.

So what does a chapter about an intractable problem do? It maps the border. Instead of one perfect characterization, we build a toolbox of sufficient conditions: checkable properties that guarantee a Hamilton cycle exists, even though many hamiltonian graphs satisfy none of them. The plan follows Diestel's Chapter 10: the classic sufficient conditions (Dirac, Chvátal–Erdős, Asratian–Khachatrian, Tutte)^[1], then Chvátal's complete answer to "when do the degrees alone force a tour?"^[2], and finally Fleischner's theorem on squares of graphs^[3]. Almost every theorem comes paired with an example showing it cannot be improved. That back-and-forth between theorem and counterexample is the real lesson.

New notation in this chapter

Recalled from earlier chapters, one clause each: \(|G|\) is the order of \(G\), its number of vertices; \(d(v)\) is the degree of \(v\), its number of neighbours; \(\delta(G)\) is the minimum degree, the smallest degree in the graph; \(N(v)\) is the neighbourhood of \(v\), the set of vertices joined to \(v\) by an edge; \(\alpha(G)\) is the independence number, the size of the largest set of pairwise non-adjacent vertices; \(\kappa(G)\) is the connectivity, the smallest number of vertex deletions that disconnect the graph; \(G - S\) is the graph left after deleting the vertex set \(S\) and all edges touching it; \(K^n\) is the complete graph on \(n\) vertices (Diestel's notation; many other books write \(K_n\)); and \(K_{2,3}\) is the complete bipartite graph with classes of sizes 2 and 3, all six cross edges present and no edges inside a class.

Dirac's theorem: own half the graph

What is the crudest thing that could force a Hamilton cycle? Sheer quantity of edges. If every vertex knows enough of the graph, a tour should have no way to get stuck. The founding theorem of the subject makes "enough" exact.

The proof idea is short enough to enjoy in full. First, the degree bound forces \(G\) to be connected: any two vertices either touch or have a common neighbour, because their neighbourhoods are each too big (at least \(n/2\) vertices) to avoid each other inside a graph of \(n\) vertices. Now take a longest path \(P = v_0 v_1 \dots v_k\). Every neighbour of the endpoint \(v_0\) must lie on \(P\): if \(v_0\) had a neighbour off the path, we could extend \(P\) and it was not longest. The same holds for the other endpoint \(v_k\).

Now count. Among the \(k \lt n\) edges of the path, at least \(n/2\) have their right end adjacent to \(v_0\), and at least \(n/2\) have their left end adjacent to \(v_k\). Two sets of size \(n/2\) inside fewer than \(n\) slots must overlap: some edge \(v_i v_{i+1}\) of the path is doubly good, meaning \(v_0 v_{i+1}\) and \(v_i v_k\) are both edges of \(G\). Those two chords rewire the path into a cycle through all its vertices: travel \(v_0 \to v_{i+1} \to \dots \to v_k\), jump the chord to \(v_i\), travel backwards \(v_i \to \dots \to v_0\). Figure 10.2 shows the surgery. Finally, this cycle must contain every vertex of \(G\): if some vertex were left out, connectivity would attach it to the cycle, and unrolling the cycle at the attachment point would produce a path longer than \(P\). Contradiction, so the cycle is a Hamilton cycle.

Is the bound \(n/2\) just an artifact of the proof? No. It is exactly right, and the counterexample is worth memorizing. Take two complete graphs, each on \(\lceil n/2 \rceil\) vertices (that is \(n/2\) rounded up), and glue them together at a single shared vertex. Figure 10.3 shows the smallest case, \(n = 5\): two triangles sharing a vertex, the bowtie. Every vertex has degree at least \(\lfloor n/2 \rfloor\), which is \(n/2\) rounded down, so the graph misses Dirac's bound by the smallest possible amount. And it has no Hamilton cycle: any round trip through both halves would have to pass through the shared vertex twice, which a cycle never does. So \(n/2\) cannot be relaxed even to \(\lfloor n/2 \rfloor\). In effect, Dirac's bound is exactly high enough to guarantee the graph is 2-connected (no single vertex whose removal disconnects it), which every hamiltonian graph must be.

Two more angles: connectivity and local degrees

Degrees are one axis. What else might force a tour? A natural guess is connectivity: the minimum number of vertices you must delete to disconnect the graph, written \(\kappa(G)\) and studied in Chapter 3. A highly connected graph is hard to cut apart, so surely a tour can always find a way through?

No amount of connectivity suffices, and the counterexample family is simple. Consider the complete bipartite graphs \(K_{k,\,k+1}\): a class of \(k\) vertices, a class of \(k+1\) vertices, all cross edges. This graph is \(k\)-connected. But any cycle in it must alternate between the two classes, so it uses the small class at most \(k\) times and has length at most \(2k\): too short to cover all \(2k+1\) vertices. Figure 10.5 shows the smallest case, \(K_{2,3}\), together with the cleanest way to see its failure: deleting the two left vertices strands the three right vertices as three separate pieces. A cycle can never be shattered that badly by two deletions, so no Hamilton cycle was ever there.

Notice what witnessed the failure of \(K_{2,3}\): a large set of mutually non-adjacent vertices, namely \(\{w_1, w_2, w_3\}\). The independence number \(\alpha(G)\), the size of the largest such set (from Chapter 5), measures how spread out a graph is. \(K_{2,3}\) has \(\alpha = 3\) but \(\kappa = 2\): more spread out than it is connected. Chvátal and Erdős discovered that this comparison is exactly the right one.

The proof idea introduces a trick used throughout this chapter: travel a longest cycle in a fixed direction and study successors. Take a longest cycle \(C\), and suppose it misses some vertex. That vertex lives in some component \(D\) of \(G - C\), the graph left after removing \(C\)'s vertices. Look at the attachment points: the vertices of \(C\) that have a neighbour in \(D\). Because deleting all of them cuts \(D\) off from the rest, there are at least \(\kappa(G)\) of them. Because \(C\) is longest, no two attachment points can be consecutive on \(C\) (otherwise we could detour through \(D\) between them and lengthen the cycle). Now the punchline: the set of successors of the attachment points, one step further along \(C\), turns out to be an independent set, and it stays independent when you add one vertex of \(D\) to it. That gives an independent set of size at least \(\kappa(G) + 1 \gt \alpha(G)\), which is a contradiction. So \(C\) missed nothing, and it is a Hamilton cycle.

Both hypotheses of Dirac's theorem and the Chvátal–Erdős condition are global: they mention \(n\), or compare two whole-graph parameters. Asratian and Khachatrian found something different in kind: a condition you can check by looking only at small neighbourhoods, never at the whole graph.

A small identity makes the condition readable: \(d(u) + d(w) = |N(u) \cup N(w)| + |N(u) \cap N(w)|\), because vertices in both neighbourhoods get counted twice on the left. Feeding this in, the hypothesis forces the two ends of every induced path \(u\,v\,w\) to have at least two common neighbours: \(v\) is always one, and the condition forces a second. The proof then runs the longest-cycle machinery again: take a longest cycle \(C\), a vertex \(u\) off it with neighbour set \(V\) on \(C\), and the successor set \(V^+\). Longest-cycle arguments make each stretch \(u\,v\,v^+\) an induced path and forbid certain edges and shared neighbours around \(V^+\). Double-counting the edges between \(V\) and \(V^+\), written \(\|V, V^+\|\), then produces the absurd conclusion \(\|V, V^+\| \le \|V, V^+\| - |V|\). The full bookkeeping is in Diestel §10.1^[1].

Two things make this theorem more than a curiosity. It strictly strengthens Dirac's theorem: whenever \(\delta(G) \ge n/2\), the local condition holds automatically. And unlike any condition that mentions \(n\), it is satisfied by arbitrarily large sparse graphs, graphs whose average degree stays bounded while the graph grows. A global fraction like \(n/2\) can never certify those.

Toughness: how hard is your graph to shatter?

The deletion argument in Figure 10.5 generalizes into a necessary condition worth naming. Delete a set \(S\) of vertices from a cycle: the cycle falls apart into at most \(|S|\) arcs. So if \(G\) has a Hamilton cycle, deleting any \(S\) can leave at most \(|S|\) components. Turning that into a graded scale:

Every hamiltonian graph is 1-tough; that is the cycle-into-arcs argument above. \(K_{2,3}\) is not 1-tough (two deletions, three pieces), which is precisely how Figure 10.5 convicted it. The natural follow-up question has been open for half a century.

What is known: 1-tough is not enough (small counterexamples exist), and for decades the conjecture was expected to hold with \(t = 2\), until Bauer, Broersma and Veldman disproved the \(t = 2\) case in 2000^[1]. The general conjecture remains open in both directions: no value of \(t\) is known to work, and no proof exists that all values fail. It is the surviving candidate for a structural converse to the easiest necessary condition. Beyond Hamilton cycles, toughness is a useful vocabulary item in its own right: it puts a number on how many vertex failures a network can absorb before fragmenting into many pieces.

Planarity's surprise: Tutte and the four colour connection

The strangest chapter in the history of Hamilton cycles is their entanglement with the four colour theorem, the statement (from Chapter 5) that every map can be coloured with four colours. In the 1880s, Tait had a proof strategy built on tours. Through the flow theory of Chapter 6, the four colour theorem is equivalent to a statement about planar cubic graphs, graphs drawable without crossings in which every vertex has degree 3; and for such graphs, "bridgeless" can be upgraded to "3-connected". Hamiltonian graphs pass the relevant flow test automatically. So if every 3-connected planar cubic graph were hamiltonian, the four colour theorem would follow, and Tait believed exactly that^[1].

It took sixty years to find out he was wrong. In 1946, Tutte constructed a 3-connected planar cubic graph with no Hamilton cycle, demolishing the premise. But ten years later Tutte salvaged what is true, and it is remarkable in its own right:

Hold this against the earlier counterexamples. The graphs \(K_{k,\,k+1}\) showed that \(k\)-connectedness never forces hamiltonicity, for any \(k\). Yet those graphs are wildly non-planar for large \(k\). Inside the plane, connectivity 4 suffices, and Tutte's 1946 counterexample shows 3 does not: the theorem is best possible. The proof is the deepest in this part of the theory and beyond this course; Diestel §10.1 gives the statement and its history^[1].

One outlook item, connecting to Chapter 8. For infinite graphs, "cycle through all vertices" seems meaningless: finite cycles cannot pass through infinitely many vertices. The repair is topological. Add to the graph its ends, the points at infinity where infinite one-way paths converge; in the resulting space, a Hamilton circle is a copy of the geometric circle passing through every vertex. A doubly infinite path, for instance, closes up into a circle through its two ends. Bruhn conjectured that Tutte's theorem survives the leap: every locally finite (each vertex has finitely many neighbours) 4-connected planar graph should have a Hamilton circle. That conjecture is open^[1].

Chvátal's theorem: when degrees alone decide

Dirac's theorem reads one number off the graph, the minimum degree. But a graph carries a full roster of degrees, and it seems wasteful to judge it by its weakest member alone. Can a few low-degree vertices be excused if enough high-degree vertices compensate? This section states the complete answer.

The counterexample in Figure 10.6 is one instance of the machine that proves the "only if" half of Chvátal's theorem. Suppose the test fails at position \(h\): the weakness \(a_h \le h\) is unpaid, meaning \(a_{n-h} \le n-h-1\). Build this graph: take a complete graph on \(n - h\) vertices, pick \(h\) of its vertices as hubs, and attach \(h\) new outer vertices, each joined to all \(h\) hubs and nothing else. The degree sequence works out to \(h\) (repeated \(h\) times), then \(n-h-1\) (repeated \(n-2h\) times), then \(n-1\) (repeated \(h\) times), which is pointwise greater than the failing sequence. Yet deleting the \(h\) hubs strands the \(h\) outer vertices individually, plus the rest of the complete part: \(h+1\) components from \(h\) deletions. Not 1-tough, hence not hamiltonian. For \(n = 5\), \(h = 2\), this is exactly Figure 10.6. The toughness idea from the last section is doing the demolition work here; the chapter's threads braid together.

The "if" half is a maximality argument in the style of Dirac's proof, with a sharper count: assume some graph above a passing floor is not hamiltonian, take one with the most edges, and derive a contradiction from a carefully chosen non-adjacent pair of high-degree vertices. Diestel §10.2 has the details^[2]. Chvátal's theorem swallows Dirac's whole: the constant floor \((\lceil n/2 \rceil, \dots, \lceil n/2 \rceil)\) passes the test instantly, since no entry is ever weak.

One corollary rounds out the story. Which degree floors force a Hamilton path, the one-way version? The trick is the join \(G * K^1\): add one new vertex adjacent to everything. Hamilton paths in \(G\) correspond exactly to Hamilton cycles in \(G * K^1\), since the new vertex can close any path into a loop. Pushing a sequence through this correspondence shifts the arithmetic by one, and out comes the answer: \((a_1,\dots,a_n)\) with \(n \ge 2\) is path-hamiltonian (every graph above it has a Hamilton path) if and only if every \(i \le n/2\) satisfies \(a_i \lt i \Rightarrow a_{n+1-i} \ge n-i\)^[2].

Fleischner's theorem: squaring the graph

The chapter's final act changes the question. Instead of asking which graphs are hamiltonian, it asks: how little must we help a graph before it becomes hamiltonian? The helping operation is beautifully natural.

Squares are generous: could squaring make every connected graph hamiltonian? No, and the counterexample is a seven-vertex spider. Take a centre \(c\) with three legs, each a path of length two: \(c\)–\(m_i\)–\(\ell_i\) for \(i = 1, 2, 3\). In the square, each foot \(\ell_i\) is adjacent to exactly two vertices: its own knee \(m_i\) (distance 1) and the centre \(c\) (distance 2). A cycle uses exactly two edges at every vertex it visits, so at each foot, a Hamilton cycle would be forced to use both available edges, including all three foot-to-centre shortcuts \(\ell_1 c\), \(\ell_2 c\), \(\ell_3 c\). That puts three cycle edges at the single vertex \(c\): impossible. Figure 10.8 shows the collision.

What went wrong with the spider? Its centre is a cut vertex, a single vertex whose removal disconnects the graph. Fleischner's theorem says that this is the only obstruction:

Mind the logic of the statement. The hypothesis is on \(G\), the conclusion on \(G^2\). \(K_{2,3}\) is 2-connected and not hamiltonian; no contradiction, the theorem promises a tour in its square only. And 2-connectedness is sufficient, not necessary: the path in Figure 10.7 is not 2-connected, yet its square is hamiltonian.

For decades Fleischner's theorem had only long, hard proofs. The short modern proof, due to Georgakopoulos, is a bridge between this chapter's two grand tours: it builds the Hamilton cycle of \(G^2\) out of an Euler tour, the easy kind of tour from Chapter 1. Three pieces of vocabulary describe the machinery. A pass of a closed walk through a vertex \(x\) is one visit: the incoming edge, then \(x\), then the outgoing edge. Lifting a pass \(u\,x\,v\) means cutting out the visit: replace the two edges \(ux\), \(xv\) by the single shortcut edge \(uv\). The point of squaring is exactly that this shortcut is available: \(u\) and \(v\) are both neighbours of \(x\) in \(G\), so their distance in \(G\) is at most 2, so \(uv\) is an edge of \(G^2\). Figure 10.9 shows one lift. Finally, a \(C\)-trail, for a fixed cycle \(C\), is a side excursion attached to \(C\): either a path meeting \(C\) exactly in its two endpoints, or a loop touching \(C\) in exactly one vertex.

Here is the sketch, with the full argument in Diestel §10.3^[3]. The claim is strengthened for induction: for any prescribed vertex \(x\), the square has a Hamilton cycle whose two edges at \(x\) are genuine edges of \(G\). A helper result (Lemma 10.3.2) provides the anchor: in any 2-connected graph, through any chosen vertex \(x\), there is a cycle \(C\) that also contains some other vertex \(y\) all of whose \(G\)-neighbours lie on \(C\). The vertices left outside \(C\) are then swept up by \(C\)-trails living in the square, obtained by applying the induction hypothesis to shrunken pieces of the graph. Next, parity: some edges of \(C\) are doubled (a path with doubled edges is called a multipath) so that every vertex ends up with even degree in the assembled multigraph. Even degrees buy an Euler tour, a closed walk using every edge exactly once but possibly visiting vertices several times. The finale is surgery: at every vertex, all passes but one are lifted, as in Figure 10.9. A careful marking scheme chooses which pass each vertex keeps, arranged so that no edge is ever lifted at both of its ends at once. After all lifts, the walk meets every vertex exactly once: a Hamilton cycle of \(G^2\), and the anchor \(y\) is what makes the bookkeeping at \(x\) come out right.

Two postscripts. For third powers the hypothesis collapses entirely: \(G^3\) is hamiltonian for every connected \(G\) with at least three vertices; three-step shortcuts can vault even over a cut vertex like the spider's. And the theorem survives infinity: Georgakopoulos proved in 2009 that the square of every 2-connected locally finite graph has a Hamilton circle, a tour through the ends in the sense of Chapter 8. The short finite proof sketched above was found as a by-product of that infinite result^[3].

The chapter closes with a conjecture that ties its first theorem to its last. Dirac's bound \(n/2\) forces a Hamilton cycle: a tour whose first power sits in \(G\). What would force a Hamilton cycle whose square sits in \(G\), meaning every pair of vertices two apart along the tour is also adjacent?

The ladder and the frontier

Step back and the chapter has a shape. One necessary condition came cheap: hamiltonian graphs are 1-tough, and its little cousin, 2-connectedness, follows. Sufficiency came as a ladder of theorems, each seeing graphs the previous one missed: Dirac's global degree bound, strengthened by the local condition of Asratian and Khachatrian, subsumed on the degree axis by Chvátal's exact test, and generalized upward by Seymour's conjecture. Off the degree axis sit the Chvátal–Erdős comparison \(\alpha \le \kappa\), Tutte's planar theorem, and Fleischner's square theorem. Between the necessary and the sufficient lies a strip of open territory where the Toughness Conjecture lives.

Where next? The hardness story, why "no good characterization" can be made precise and what NP-completeness really says, is taken up with the right vocabulary in Chapter 12. And there is a probabilistic sequel: Chapter 11 asks when a random graph becomes hamiltonian, and the threshold answers echo Dirac's degree condition in probabilistic clothing. The tour goes on.