40.04.11 · combinatorics / graph-theory-core

Hamilton Cycles: Dirac, Ore, and Chvátal-Erdős

shipped3 tiersLean: none

Anchor (Master): Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §10.1-§10.2; Bondy-Murty 2008 (Springer GTM 244) Ch. 18 (closure, Chvátal's condition, pancyclicity, toughness); Bollobás 2001 *Random Graphs* (2nd ed., Cambridge) Ch. 8 (Hamiltonicity thresholds); the original sources Dirac 1952, Ore 1960, Bondy-Chvátal 1976, Chvátal 1972, Chvátal-Erdős 1972, Tutte 1946, Komlós-Szemerédi 1983

Intuition Beginner

Imagine a delivery driver who must visit every house in a neighbourhood exactly once and end back at the depot. The roads form a network: dots for houses, lines for the roads between them. The driver wants a single closed loop that touches every house once and only once. Such a loop is called a Hamilton cycle, named for the mathematician who studied a puzzle of this kind on a dodecahedron. Whether one exists turns out to be a surprisingly hard question.

It helps to compare this with a different-sounding task: cross every road exactly once, rather than visit every house. That second task has a clean answer. A network has a tour crossing every road once exactly when every house has an even number of roads meeting it. The road-tour question is settled by a quick local count. The house-visit question has no such shortcut. You can stare at a network, check every dot's road-count, and still not know whether a single loop reaching all the houses exists.

So mathematicians look for conditions that guarantee a Hamilton cycle without having to search. The simplest is about crowding. If every house has roads to at least half of all the other houses, a full loop must exist. With that much connection, you can always weave the houses into one closed tour. The chapter is the study of such guarantees and of the stubborn networks that just barely escape them.

Visual Beginner

Picture six houses arranged in a circle: $v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6}$ . Suppose each house has a road to its two circle-neighbours and also to the house directly across the circle. So $v_{1}$ connects to $v_{2}$ , $v_{6}$ , and $v_{4}$ , and similarly for the rest. Every house has exactly three roads, and three is half of the six houses minus the house itself rounded up, so the crowding rule is comfortably met.

The bold loop around the outside, $v_{1} v_{2} v_{3} v_{4} v_{5} v_{6} v_{1}$ , visits all six houses once and returns to the start. That is a Hamilton cycle. The table beside the picture lists, for each house, the three houses it reaches.

house	roads go to
$v_{1}$	$v_{2}, v_{6}, v_{4}$
$v_{2}$	$v_{1}, v_{3}, v_{5}$
$v_{3}$	$v_{2}, v_{4}, v_{6}$

Each house reaching three of the other five is more than the half-of-everyone the rule asks for, and so a closed tour through every house is forced to exist. The bold hexagon is one such tour.

Worked example Beginner

Take five houses $a, b, c, d, e$ with these roads: $a - b$ , $b - c$ , $c - d$ , $d - e$ , $e - a$ (a five-house ring), plus two extra roads $a - c$ and $b - d$ . We hunt for a single closed loop visiting every house once.

Step 1. Count roads at each house. House $a$ : roads to $b, e, c$ , so three. House $b$ : roads to $a, c, d$ , so three. House $c$ : roads to $b, d, a$ , so three. House $d$ : roads to $c, e, b$ , so three. House $e$ : roads to $d, a$ , so two.

Step 2. Check the crowding rule. Half of the five houses is two and a half, so the rule asks each house to reach at least two and a half, meaning at least three other houses. House $e$ reaches only two. The rule is not met, so it gives us no guarantee either way. We must look by hand.

Step 3. Try to build a loop. Start at $e$ . Its only roads go to $d$ and $a$ , so any loop through $e$ must enter from one and leave to the other: the loop uses the segment $a - e - d$ (or its reverse).

Step 4. Continue from $d$ . We came from $e$ , so go onward to $c$ or $b$ . Try $d - c$ . From $c$ go to $b$ (since $a$ is saved for the end). Then $b - a$ closes back to the start of our segment. The loop is $e, d, c, b, a, e$ .

Step 5. Verify. The loop $e - d - c - b - a - e$ uses roads $e - d$ , $d - c$ , $c - b$ , $b - a$ , $a - e$ , all present, and visits each of the five houses exactly once before returning to $e$ .

What this tells us: the crowding rule failed here, yet a Hamilton cycle still existed. The rule is a one-way guarantee. When it holds, a loop is certain; when it fails, a loop may or may not exist, and only a direct search settles it.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $G = (V, E)$ is a finite simple graph with $n = ∣ V ∣ \geq 3$ . A Hamilton cycle (or Hamiltonian cycle) is a cycle that contains every vertex of $G$ ; equivalently a cyclic ordering $v_{1} v_{2} \dots v_{n} v_{1}$ of all of $V$ with $v_{i} v_{i + 1} \in E$ for each $i$ (indices mod $n$ ). A Hamilton path is a path containing every vertex. A graph possessing a Hamilton cycle is Hamiltonian, and one possessing a Hamilton path is traceable. The contrast with an Euler tour — a closed walk traversing every edge exactly once, which exists iff $G$ is connected and every degree is even — is structural: Eulerianity is a local degree-parity condition decidable in linear time, while deciding Hamiltonicity is NP-complete ^{[Diestel 2017 §10.1]}. No characterisation of Hamiltonian graphs comparable to the Euler criterion is expected; the theory instead supplies sufficient conditions and obstructions.

Write $δ (G)$ for the minimum degree, $κ (G)$ for the vertex-connectivity (the smallest number of vertices whose deletion disconnects $G$ or leaves a single vertex), and $α (G)$ for the independence number (the largest set of pairwise non-adjacent vertices). Ore's condition is the requirement that $de g (u) + de g (v) \geq n$ for every pair of non-adjacent vertices $u, v$ . The Bondy-Chvátal closure $cl (G)$ is the graph obtained from $G$ by repeatedly joining any two non-adjacent vertices whose degree sum is at least $n$ , until no such pair remains ^{[Bondy-Chvátal 1976]}. A graph $G$ on $n$ vertices is said to satisfy Chvátal's condition if its degree sequence $d_{1} \leq d_{2} \leq \dots \leq d_{n}$ has, for every $i < n /2$ , either $d_{i} > i$ or $d_{n - i} \geq n - i$ .

The toughness $t (G)$ of a non-complete graph is $$ t(G) = \min_{S} \frac{|S|}{c(G - S)}, $$ the minimum taken over vertex sets $S$ whose removal disconnects $G$ , where $c (G - S)$ is the number of connected components of $G - S$ ; one sets $t (K_{n}) = \infty$ . A graph is $t$ -tough if its toughness is at least $t$ . Finally $G$ is Hamilton-connected if every pair of vertices is joined by a Hamilton path, and pancyclic if it contains cycles of every length from $3$ to $n$ .

Counterexamples to common slips

Hamiltonicity is not Eulerianity. The complete bipartite graph $K_{2, 3}$ has all even degrees on neither side and is not Eulerian, yet the question of whether it is Hamiltonian is separate; in fact $K_{2, 3}$ is non-Hamiltonian (it has independence number $3 > 2 = κ$ ), illustrating that the two properties are logically independent.
Dirac's bound $n /2$ is tight. Two copies of $K_{(n + 1) /2}$ sharing a single vertex (for odd $n$ ) have minimum degree just below $n /2$ and no Hamilton cycle, since the shared vertex is a cutvertex; one cannot lower the threshold.
Ore is weaker than Dirac as a hypothesis but stronger as a theorem. Every graph meeting Dirac's $δ \geq n /2$ meets Ore's condition (non-adjacent $u, v$ each have degree $\geq n /2$ ), so Ore's theorem implies Dirac's; the converse implication of hypotheses fails.
A Hamiltonian graph need not be pancyclic. The complete bipartite graph $K_{n /2, n /2}$ is Hamiltonian but contains no odd cycle, hence no triangle; pancyclicity is a strictly stronger conclusion, and Bondy's theorem (below) recovers it under a slightly strengthened hypothesis with $K_{n /2, n /2}$ as the sole exception.

Key theorem with proof Intermediate+

Theorem (Dirac and Ore). Let $G$ be a graph on $n \geq 3$ vertices.

(a) Ore, 1960. If $de g (u) + de g (v) \geq n$ for every pair of non-adjacent vertices $u, v$ , then $G$ is Hamiltonian.

(b) Dirac, 1952. If $δ (G) \geq n /2$ , then $G$ is Hamiltonian.

(See ^{[Ore 1960]}, ^{[Dirac 1952]}, ^{[Diestel 2017 §10.1]}.)

Proof. Part (b) follows from part (a): if $δ (G) \geq n /2$ and $u, v$ are non-adjacent, then $de g (u) + de g (v) \geq n /2 + n /2 = n$ , so Ore's hypothesis holds. It remains to prove (a).

Suppose Ore's condition holds but $G$ is not Hamiltonian. Add edges to $G$ one at a time, as long as the result stays non-Hamiltonian, to obtain an edge-maximal non-Hamiltonian graph $G^{'}$ on the same vertex set; adding edges only raises degrees, so $G^{'}$ still satisfies Ore's condition. Since $n \geq 3$ , $G^{'}$ is not complete (the complete graph is Hamiltonian), so there are non-adjacent vertices $u, v$ in $G^{'}$ . By maximality, $G^{'} + uv$ has a Hamilton cycle, and that cycle must use the new edge $uv$ ; deleting $uv$ from it leaves a Hamilton path $u = x_{1}, x_{2}, \dots, x_{n} = v$ in $G^{'}$ from $u$ to $v$ .

Consider the index sets $$ A = { i : u x_{i+1} \in E(G') }, \qquad B = { i : v x_i \in E(G') }, $$ both subsets of ${1, \dots, n - 1}$ . Then $∣ A ∣ = de g (u)$ and $∣ B ∣ = de g (v)$ , so $∣ A ∣ + ∣ B ∣ = de g (u) + de g (v) \geq n > n - 1 = ∣ {1, \dots, n - 1} ∣$ . By pigeonhole $A \cap B \neq = \emptyset$ : there is an index $i$ with $u x_{i + 1} \in E (G^{'})$ and $v x_{i} \in E (G^{'})$ . Now form the cycle $$ u, x_2 \cdots x_i, v, x_{n-1} \cdots x_{i+1}, u, $$ which follows the Hamilton path from $u = x_{1}$ to $x_{i}$ , jumps via $v x_{i}$ to $v = x_{n}$ , traverses the path backward from $x_{n}$ to $x_{i + 1}$ , and closes via $u x_{i + 1}$ . This visits every vertex once and is a Hamilton cycle in $G^{'}$ , contradicting that $G^{'}$ is non-Hamiltonian. Hence $G$ is Hamiltonian. $□$

Bridge. This proof builds toward the entire degree-condition theory and appears again in the closure operation, the Chvátal degree-sequence theorem, and the Chvátal-Erdős theorem, because the rotation that converts a Hamilton path into a Hamilton cycle is the foundational reason every sufficient condition in the chapter takes a degree-sum or connectivity-versus-independence form. The pigeonhole crossing $u x_{i + 1}, v x_{i}$ is exactly the mechanism Bondy and Chvátal isolated as edge-stability: if $de g (u) + de g (v) \geq n$ then $G$ is Hamiltonian precisely when $G + uv$ is, which is the central insight that lets one add edges freely up to the closure. This is exactly how Dirac generalises to Ore and Ore generalises to Chvátal's condition — each weakens what must hold while preserving the same path-rotation engine. The bridge is that the crossing pair $x_{i}, x_{i + 1}$ found here is the same crossing a closure step exploits, so putting these together the closure is just Ore's argument applied repeatedly until no addable pair remains.

Exercises Intermediate+

Exercise 6 (medium, short-answer).

Prove that if $de g (u) + de g (v) \geq n$ for a non-adjacent pair $u, v$ in $G$ , then $G$ is Hamiltonian if and only if $G + uv$ is. (This is the single closure step.)

Hint

One direction is immediate. For the other, suppose $G + uv$ has a Hamilton cycle using $uv$ and rerun the Ore pigeonhole rotation.

Answer

If $G$ is Hamiltonian then so is the supergraph $G + uv$ . Conversely suppose $G + uv$ is Hamiltonian. If a Hamilton cycle avoids $uv$ it lies in $G$ and we are done. Otherwise every Hamilton cycle of $G + uv$ uses $uv$ ; deleting that edge gives a Hamilton path $u = x_{1}, \dots, x_{n} = v$ in $G$ . With $A = {i : u x_{i + 1} \in E (G)}$ , $B = {i : v x_{i} \in E (G)}$ , both inside ${1, \dots, n - 1}$ and $∣ A ∣ + ∣ B ∣ = de g_{G} (u) + de g_{G} (v) \geq n > n - 1$ , pigeonhole gives $i$ with $u x_{i + 1}, v x_{i} \in E (G)$ , and the rotation $u x_{2} \dots x_{i} v x_{n - 1} \dots x_{i + 1} u$ is a Hamilton cycle in $G$ . Rubric: full credit for both directions, with the rotation argument for the reverse.

Exercise 7 (hard, short-answer).

Prove that the Bondy-Chvátal closure $cl (G)$ is well-defined: the graph obtained by repeatedly adding edges between non-adjacent degree-sum- $\geq n$ pairs does not depend on the order of additions.

Hint

Adding edges only increases degrees, so a pair eligible at some stage stays eligible. Compare any two completed sequences edge by edge.

Answer

Let $G_{1}, G_{2}$ be two graphs reached by running the process to termination via different orders of additions; each is $G$ plus some added edges, with no addable pair remaining. Claim every edge added in the first sequence is present in $G_{2}$ . Order the first sequence's additions $e_{1}, e_{2}, \dots$ and suppose $e_{k} = uv$ is the first not in $G_{2}$ . When $e_{k}$ was added, $de g (u) + de g (v) \geq n$ in $G \cup {e_{1}, \dots, e_{k - 1}}$ , and by the minimality of $k$ all of $e_{1}, \dots, e_{k - 1}$ lie in $G_{2}$ , so degrees in $G_{2}$ are at least as large, giving $de g_{G_{2}} (u) + de g_{G_{2}} (v) \geq n$ with $u, v$ non-adjacent in $G_{2}$ — contradicting that $G_{2}$ has no addable pair. Hence $G_{1} \subseteq G_{2}$ , and by symmetry $G_{2} \subseteq G_{1}$ , so $G_{1} = G_{2}$ . Rubric: full credit for the monotone-degree first-difference argument and the symmetric closure.

Exercise 8 (hard, short-answer).

Deduce Chvátal's degree-sequence theorem's easy direction: if $G$ has degree sequence $d_{1} \leq \dots \leq d_{n}$ and for every $i < n /2$ either $d_{i} > i$ or $d_{n - i} \geq n - i$ , exhibit how the closure $cl (G)$ becomes complete, hence $G$ is Hamiltonian.

Hint

Suppose $cl (G)$ is not complete; take a non-adjacent pair $u, v$ in it with maximum degree sum and bound how many vertices have small degree.

Answer

Pass to $H = cl (G)$ ; it inherits a degree sequence dominating that of $G$ , so Chvátal's condition still holds in $H$ . If $H$ is complete it is Hamiltonian, and by the closure stability (Exercise 6 iterated) so is $G$ . Otherwise pick non-adjacent $u, v \in H$ with $de g (u) \leq de g (v)$ and $de g (u) + de g (v)$ maximum among non-adjacent pairs; closure-termination forces $de g (u) + de g (v) \leq n - 1$ . Set $i = de g (u)$ . Every vertex non-adjacent to $v$ (other than $v$ ) has degree $\leq de g (u) = i$ by the maximality choice, and there are at least $n - 1 - de g (v) \geq i$ such vertices, giving $d_{i} \leq i$ . Likewise the vertices non-adjacent to $u$ have degree $\leq de g (v) \leq n - 1 - i$ , and there are at least $i + 1$ of them together with $u$ , forcing $d_{n - i} \leq n - 1 - i < n - i$ . Then $i < n /2$ with $d_{i} \leq i$ and $d_{n - i} < n - i$ contradicts Chvátal's condition. Hence $H$ is complete and $G$ is Hamiltonian. Rubric: full credit for reducing to the closure, the extremal non-adjacent pair, and the contradiction with the stated condition.

Advanced results Master

Theorem (Bondy-Chvátal closure and Chvátal's degree-sequence condition). A graph $G$ is Hamiltonian if and only if its closure $cl (G)$ is Hamiltonian; in particular if $cl (G) = K_{n}$ then $G$ is Hamiltonian. Consequently, if the degree sequence $d_{1} \leq \dots \leq d_{n}$ satisfies, for each $i < n /2$ , $d_{i} > i$ or $d_{n - i} \geq n - i$ , then $G$ is Hamiltonian, and this monotone condition is best possible: whenever it fails there is a non-Hamiltonian graph whose degree sequence is dominated entrywise by one violating it. (Bondy-Chvátal ^{[Bondy-Chvátal 1976]}; Chvátal ^{[Chvátal 1972]}; Bondy-Murty ^{[Bondy-Murty 2008 Ch. 18]}.) The stability theorem is the single closure step (the Ore rotation) iterated, and well-definedness of $cl (G)$ rests on the monotonicity of degrees under edge addition. Chvátal's condition is optimal in a precise sense: among all conditions phrased purely on a sorted degree sequence and closed under domination, it is the weakest that still forces Hamiltonicity, so Dirac's $δ \geq n /2$ and Ore's degree-sum condition are both strict specialisations sitting inside it.

Theorem (Chvátal-Erdős, 1972). If $κ (G) \geq α (G)$ and $n \geq 3$ , then $G$ is Hamiltonian. (Chvátal-Erdős ^{[Chvátal-Erdős 1972]}; Diestel ^{[Diestel 2017 §10.1]}.) This is the bridge between connectivity and independence: take a longest cycle $C$ and suppose, for contradiction, it omits a vertex. The fan lemma (a consequence of Menger's theorem, the prerequisite material of 40.04.04) supplies $κ (G)$ paths from an off-cycle vertex $w$ to $C$ , meeting $C$ in $κ (G)$ distinct vertices; the successors (along a fixed orientation of $C$ ) of these attachment points, together with $w$ , form an independent set of size $κ (G) + 1 > α (G)$ — for two such successors joined by an edge, or one joined to $w$ , would yield a longer cycle by rerouting. That contradicts the definition of $α (G)$ , so $C$ spans $G$ . Connectivity at least the independence number is incomparable with the degree conditions: it captures expander-like graphs of modest degree that Dirac and Ore miss.

Theorem (Bondy's meta-conjecture, pancyclicity). Almost every sufficient condition for Hamiltonicity in fact forces pancyclicity, with a small number of exceptions. Concretely (Bondy 1971): if $G$ satisfies Ore's condition then $G$ is pancyclic or $G = K_{n /2, n /2}$ . (Bondy-Murty ^{[Bondy-Murty 2008 Ch. 18]}.) The proof finds, inside the Hamilton cycle guaranteed by Ore, chords that cut out cycles of every intermediate length, the balanced complete bipartite graph being the unique structure rigid enough to block all odd lengths. The meta-principle has been verified for the Chvátal-Erdős condition and for many spectral and toughness conditions, and remains a guiding heuristic rather than a single theorem.

Theorem (toughness, and Hamiltonicity in dense and random settings). Every Hamiltonian graph is $1$ -tough; Chvátal's $1976$ toughness conjecture asserts a constant $t_{0}$ such that every $t_{0}$ -tough graph is Hamiltonian, and Bauer-Broersma-Veldman (2000) showed $t_{0} \geq 9/4$ is necessary, refuting $t_{0} = 2$ . In the random graph $G (n, p)$ , the threshold for Hamiltonicity coincides with the disappearance of vertices of degree $\leq 1$ : Komlós-Szemerédi (1983) and Bollobás (1984) proved that if $p = (ln n + ln ln n + c_{n}) / n$ then $G (n, p)$ is Hamiltonian with probability tending to $1$ iff $c_{n} \to \infty$ , the same $ln n / n$ scale at which the graph becomes connected (the second-moment threshold material of 40.07.03). Dirac-type theorems extend to hypergraphs (Rödl-Ruciński-Szemerédi) and to the Pósa-Seymour conjecture on cycle powers, all proved by absorption refinements of the rotation argument. (Bollobás ^{[Bondy-Murty 2008 Ch. 18]}; Diestel ^{[Diestel 2017 §10.2]}.)

Synthesis. Putting these together, the chapter is one engine — the path-rotation that converts a near-spanning path or cycle into a spanning one — read under three kinds of hypothesis: degree, connectivity, and density. The central insight is that the Ore rotation, the closure, and the Chvátal-Erdős longest-cycle argument all certify a Hamilton cycle by deriving a contradiction from its absence, and this is exactly the same min-max move that connectivity theory uses, since the Chvátal-Erdős proof is the fan lemma of Menger's theorem in disguise. The foundational reason the degree and connectivity conditions are incomparable is that the closure operation generalises Dirac and Ore into Chvátal's optimal monotone condition, while $κ \geq α$ is dual to it — degree conditions bound local crowding, connectivity-versus-independence bounds global obstruction — so neither contains the other, yet both feed the same conclusion. The bridge is that toughness $t (G) \geq 1$ is the universal necessary condition every sufficient condition must respect, and the random-graph threshold shows the true boundary sits exactly where the last degree- $1$ vertex vanishes, so the deterministic guarantees are conservative shadows of a sharp probabilistic law. This generalises the connectivity chapter's certify-by-obstruction principle into the hardest decision problem of the area, the one whose worst case is NP-complete and whose travelling-salesman incarnation drives combinatorial optimisation.

Full proof set Master

Proposition 1 (Ore's theorem). If $G$ on $n \geq 3$ vertices satisfies $de g (u) + de g (v) \geq n$ for all non-adjacent $u, v$ , then $G$ is Hamiltonian.

Proof. Suppose not, and let $G^{'}$ be an edge-maximal non-Hamiltonian supergraph of $G$ on $V$ ; degrees only grow, so $G^{'}$ still satisfies Ore's condition. As $K_{n}$ is Hamiltonian ( $n \geq 3$ ), $G^{'} \neq = K_{n}$ , so fix non-adjacent $u, v$ in $G^{'}$ . By maximality $G^{'} + uv$ is Hamiltonian, and a Hamilton cycle there uses $uv$ (else it lies in $G^{'}$ ); deleting $uv$ yields a Hamilton path $u = x_{1}, \dots, x_{n} = v$ . Put $A = {i \in [n - 1] : u x_{i + 1} \in E (G^{'})}$ and $B = {i \in [n - 1] : v x_{i} \in E (G^{'})}$ . Then $∣ A ∣ = de g_{G^{'}} (u)$ , $∣ B ∣ = de g_{G^{'}} (v)$ , and $∣ A ∣ + ∣ B ∣ \geq n > ∣ [n - 1] ∣$ , so some $i \in A \cap B$ . The closed walk $u x_{2} \dots x_{i} v x_{n - 1} \dots x_{i + 1} u$ uses the edges $u x_{i + 1}$ and $v x_{i}$ and the path edges, visiting each vertex once: a Hamilton cycle of $G^{'}$ , contradiction. $□$

Proposition 2 (closure stability). If $de g_{G} (u) + de g_{G} (v) \geq n$ for non-adjacent $u, v$ , then $G$ is Hamiltonian iff $G + uv$ is. Consequently $G$ is Hamiltonian iff $cl (G)$ is.

Proof. Forward is monotone (a Hamilton cycle of $G$ survives in $G + uv$ ). For the reverse, if $G + uv$ has a Hamilton cycle avoiding $uv$ it is already a cycle of $G$ ; otherwise every Hamilton cycle uses $uv$ , and deleting it gives a Hamilton $u$ – $v$ path, whence the Proposition 1 pigeonhole rotation (with degrees taken in $G$ , using $de g_{G} (u) + de g_{G} (v) \geq n$ ) produces a Hamilton cycle inside $G$ . Iterating over the finitely many closure additions, and noting each added pair had degree sum $\geq n$ at the moment of addition, gives $G$ Hamiltonian iff $cl (G)$ is. Well-definedness of $cl (G)$ : degrees are non-decreasing under additions, so a pair eligible at one stage stays eligible; a first-difference argument between two termination orders (an edge added in one but absent in the other still has degree sum $\geq n$ there, contradicting termination) forces the two results equal. $□$

Proposition 3 (Chvátal-Erdős theorem). If $κ (G) \geq α (G)$ and $n \geq 3$ then $G$ is Hamiltonian.

Proof. Write $k = κ (G) \geq 1$ , so $G$ is connected. Let $C$ be a longest cycle, oriented, and suppose $C \neq = G$ , so some vertex $w \in / C$ exists. Since $G$ is $k$ -connected, the fan version of Menger's theorem (40.04.04) gives $k$ paths $P_{1}, \dots, P_{k}$ from $w$ to $C$ , pairwise disjoint except at $w$ , each meeting $C$ only in its endpoint; let $a_{1}, \dots, a_{k}$ be the distinct landing vertices on $C$ and $a_{i}^{+}$ the successor of $a_{i}$ along the orientation. The set ${a_{1}^{+}, \dots, a_{k}^{+}, w}$ has $k + 1$ vertices. It is independent: if $a_{i}^{+} a_{j}^{+} \in E$ ( $i \neq = j$ ), rerouting $C$ through this chord and the two fan paths $P_{i}, P_{j}$ (replacing the arcs $a_{i} \to a_{i}^{+}$ and $a_{j} \to a_{j}^{+}$ ) yields a longer cycle through $w$ , contradicting maximality of $C$ ; and if $w a_{i}^{+} \in E$ , then inserting $w$ between $a_{i}$ and $a_{i}^{+}$ via $P_{i}$ and this edge lengthens $C$ . Also each $a_{i}^{+} \neq = w$ . Hence $α (G) \geq k + 1 > k = κ (G)$ , contradicting $κ \geq α$ . So $C = G$ and $G$ is Hamiltonian. $□$

Proposition 4 (Hamiltonicity forces $1$ -toughness). If $G$ is Hamiltonian then $c (G - S) \leq ∣ S ∣$ for every $\emptyset \neq = S \subseteq V$ , so $t (G) \geq 1$ .

Proof. Let $C$ be a Hamilton cycle. Deleting the $∣ S ∣$ vertices of $S$ from the cycle $C$ leaves at most $∣ S ∣$ openings, splitting $C$ into at most $∣ S ∣$ paths (arcs), so $C - S$ has at most $∣ S ∣$ components. Each component of $G - S$ contains at least one full arc of $C - S$ (every vertex outside $S$ lies on $C$ ), so $c (G - S) \leq c (C - S) \leq ∣ S ∣$ . As $S$ ranges over all separating sets, $t (G) = min_{S} ∣ S ∣/ c (G - S) \geq 1$ . $□$

Proposition 5 (Dirac's bound is sharp; Tutte's planar counterexample). For every odd $n \geq 5$ there is a non-Hamiltonian graph with $δ = (n - 1) /2$ , and there exists a $3$ -connected cubic planar non-Hamiltonian graph (Tutte's graph), refuting Tait's conjecture.

Proof. For sharpness, take $G$ to be two copies of $K_{(n + 1) /2}$ glued at a single shared vertex $z$ . Then $n = 2 \cdot \frac{n + 1}{2} - 1$ , each non-shared vertex has degree $\frac{n + 1}{2} - 1 = \frac{n - 1}{2}$ , and $z$ is a cutvertex; deleting $z$ gives two components, so $c (G - z) = 2 > 1 = ∣ {z} ∣$ , violating Proposition 4, hence $G$ is non-Hamiltonian while $δ = (n - 1) /2$ , just under $n /2$ . For the planar statement, Tutte ^{[Tutte 1946]} constructed a $3$ -connected cubic planar graph on $46$ vertices built from three copies of a fragment (the "Tutte fragment") around a central triangle; a parity/forced-edge argument on the fragment shows any Hamilton cycle would have to use a configuration of edges that cannot close, so no Hamilton cycle exists. This refutes Tait's $1884$ conjecture that every $3$ -connected cubic planar graph is Hamiltonian, a conjecture whose truth would have implied the four-colour theorem. $□$

Connections Master

Connectivity and Menger's theorem 40.04.04. The Chvátal-Erdős theorem is connectivity theory cashed out: its proof is the fan lemma — the Menger consequence proved in that unit — applied to a longest cycle, turning $κ (G)$ disjoint paths into an independent set of size $κ + 1$ . The toughness invariant refines the connectivity number $κ$ by weighing it against the number of components produced, and $t (G) \geq 1$ as a necessary condition for Hamiltonicity is the cut-versus-components inequality that the connectivity chapter's separators make precise; every sufficient condition in this unit must respect that bound.
Graphs, basic invariants, and the foundational lemmas 40.04.01. The contrast that frames the whole unit — Hamilton cycles versus Euler tours — lives entirely in that root chapter's vocabulary: Eulerianity is the even-degree-and-connected criterion proved there, decidable from the degree sequence, while Hamiltonicity admits no such local test. The degree-sum hypotheses of Dirac, Ore, and Chvátal are conditions on exactly the degree function and degree sequence defined in the foundational unit, and the independence number $α$ is the complement of the clique vocabulary introduced there.
Extremal graph theory: Turán and Erdős-Stone-Simonovits 40.05.01. Dirac's theorem is an extremal statement of the same family as Turán's: both ask how dense a graph must be to force a prescribed substructure, here a spanning cycle rather than a complete subgraph, and both are proved by extremal/edge-maximal arguments. The sharpness example for Dirac (two cliques sharing a vertex) is an extremal construction in the Turán spirit, and the pancyclicity refinement connects the minimum-degree threshold to the spectrum of cycle lengths an extremal graph must contain.
Probabilistic method: second moment and random-graph thresholds 40.07.03. The deterministic Dirac/Ore guarantees are conservative shadows of a sharp probabilistic law: in $G (n, p)$ the Hamiltonicity threshold sits at $p \sim ln n / n$ , exactly where the last vertex of degree $\leq 1$ disappears, proved by the second-moment and threshold machinery of that unit. The hitting-time result (a random graph process becomes Hamiltonian at the instant its minimum degree reaches $2$ ) is the precise quantitative successor of Dirac's minimum-degree heuristic.
Probabilistic method: Szele's tournament bound 40.07.02. Szele's lower bound on the number of Hamiltonian paths in a tournament, the first use of the probabilistic method, is the directed analogue of the counting questions this unit raises: where Dirac guarantees existence of one Hamilton cycle, Szele's linearity-of-expectation argument guarantees many Hamiltonian paths exist in every tournament, and the two together frame the existence-versus-enumeration dichotomy for spanning structures.

Historical & philosophical context Master

The cycle is named for William Rowan Hamilton, who in 1857 marketed the "Icosian game," a puzzle of finding a closed tour visiting every vertex of a dodecahedron once; Thomas Kirkman had posed equivalent questions on polyhedra in the same decade ^{[Bondy-Murty 2008 Ch. 18]}. The modern sufficient-condition theory begins with Gabriel Dirac's 1952 Some theorems on abstract graphs (Proceedings of the London Mathematical Society) ^{[Dirac 1952]}, proving that minimum degree at least $n /2$ forces a Hamilton cycle. Øystein Ore weakened the hypothesis to a degree-sum condition on non-adjacent pairs in a one-page 1960 note in the American Mathematical Monthly ^{[Ore 1960]}, and John Adrian Bondy and Václav Chvátal isolated the underlying stability mechanism as the closure operation in their 1976 A method in graph theory (Discrete Mathematics) ^{[Bondy-Chvátal 1976]}, unifying the prior results. Chvátal had already given the best monotone degree-sequence condition in 1972 (On Hamilton's ideals, Journal of Combinatorial Theory B) ^{[Chvátal 1972]}.

The connectivity-versus-independence criterion is due to Chvátal and Paul Erdős in their 1972 A note on Hamiltonian circuits (Discrete Mathematics) ^{[Chvátal-Erdős 1972]}, opening a line incomparable with the degree conditions. On the obstruction side, William Tutte's 1946 On Hamiltonian circuits (Journal of the London Mathematical Society) ^{[Tutte 1946]} produced the first $3$ -connected cubic planar non-Hamiltonian graph, refuting Peter Guthrie Tait's 1884 conjecture and severing a proposed route to the four-colour theorem; the non-Hamiltonicity of the Petersen graph (Julius Petersen, 1898) is the small standard witness. The probabilistic boundary was located by János Komlós and Endre Szemerédi (1983) and Béla Bollobás (1984), who pinned the $G (n, p)$ threshold to the connectivity scale $ln n / n$ , and the proof that deciding Hamiltonicity is NP-complete was given by Richard Karp in his 1972 list of twenty-one problems.

Bibliography Master

@book{Diestel2017,
  author    = {Diestel, Reinhard},
  title     = {Graph Theory},
  edition   = {5th},
  series    = {Graduate Texts in Mathematics},
  volume    = {173},
  publisher = {Springer},
  year      = {2017}
}

@book{BondyMurty2008,
  author    = {Bondy, J. A. and Murty, U. S. R.},
  title     = {Graph Theory},
  series    = {Graduate Texts in Mathematics},
  volume    = {244},
  publisher = {Springer},
  year      = {2008}
}

@article{Dirac1952,
  author  = {Dirac, Gabriel A.},
  title   = {Some theorems on abstract graphs},
  journal = {Proceedings of the London Mathematical Society},
  series  = {3},
  volume  = {2},
  year    = {1952},
  pages   = {69--81}
}

@article{Ore1960,
  author  = {Ore, {\O}ystein},
  title   = {Note on Hamilton circuits},
  journal = {American Mathematical Monthly},
  volume  = {67},
  year    = {1960},
  pages   = {55}
}

@article{BondyChvatal1976,
  author  = {Bondy, J. A. and Chv\'atal, V\'aclav},
  title   = {A method in graph theory},
  journal = {Discrete Mathematics},
  volume  = {15},
  number  = {2},
  year    = {1976},
  pages   = {111--135}
}

@article{Chvatal1972,
  author  = {Chv\'atal, V\'aclav},
  title   = {On Hamilton's ideals},
  journal = {Journal of Combinatorial Theory, Series B},
  volume  = {12},
  number  = {2},
  year    = {1972},
  pages   = {163--168}
}

@article{ChvatalErdos1972,
  author  = {Chv\'atal, V\'aclav and Erd\H{o}s, Paul},
  title   = {A note on Hamiltonian circuits},
  journal = {Discrete Mathematics},
  volume  = {2},
  number  = {2},
  year    = {1972},
  pages   = {111--113}
}

@article{Tutte1946,
  author  = {Tutte, William T.},
  title   = {On Hamiltonian circuits},
  journal = {Journal of the London Mathematical Society},
  volume  = {21},
  year    = {1946},
  pages   = {98--101}
}

@article{KomlosSzemeredi1983,
  author  = {Koml\'os, J\'anos and Szemer\'edi, Endre},
  title   = {Limit distribution for the existence of Hamiltonian cycles in a random graph},
  journal = {Discrete Mathematics},
  volume  = {43},
  number  = {1},
  year    = {1983},
  pages   = {55--63}
}

@article{Bondy1971,
  author  = {Bondy, J. A.},
  title   = {Pancyclic graphs I},
  journal = {Journal of Combinatorial Theory, Series B},
  volume  = {11},
  number  = {1},
  year    = {1971},
  pages   = {80--84}
}

@incollection{Karp1972,
  author    = {Karp, Richard M.},
  title     = {Reducibility among combinatorial problems},
  booktitle = {Complexity of Computer Computations},
  publisher = {Plenum Press},
  year      = {1972},
  pages     = {85--103}
}

Prerequisites

40.04.04

Tier anchors

beginner: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §10.1 read for the picture of a closed tour through every city and the contrast with Euler tours; West 2001 *Introduction to Graph Theory* (2nd ed., Prentice Hall) §7.2 for the travelling-salesman framing of Hamilton cycles and the small worked examples; the Petersen graph as the standard picture of a graph that resists every attempt at a single closed tour
intermediate: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §10.1 (Dirac's theorem and the longest-path rotation proof, Ore's condition, the Chvátal-Erdős theorem); Bondy-Murty 2008 *Graph Theory* (Springer GTM 244) Ch. 18 (Hamilton cycles, Dirac, Ore, the Bondy-Chvátal closure and Chvátal's degree-sequence condition); West 2001 §7.2
master: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §10.1-§10.2; Bondy-Murty 2008 (Springer GTM 244) Ch. 18 (closure, Chvátal's condition, pancyclicity, toughness); Bollobás 2001 *Random Graphs* (2nd ed., Cambridge) Ch. 8 (Hamiltonicity thresholds); the original sources Dirac 1952, Ore 1960, Bondy-Chvátal 1976, Chvátal 1972, Chvátal-Erdős 1972, Tutte 1946, Komlós-Szemerédi 1983

References

Diestel 2017 — Graph Theory (5th edition) · Springer Graduate Texts in Mathematics 173, 2017, §10.1 (Hamilton cycles and paths, Dirac's theorem with the longest-path/rotation argument, Ore's condition, the Chvátal-Erdős theorem κ ≥ α implies Hamiltonian), §10.2 (Hamilton cycles in dense and in random graphs)
Bondy, Murty 2008 — Graph Theory · Springer Graduate Texts in Mathematics 244, 2008, Ch. 18 (Hamilton cycles, Dirac and Ore, the Bondy-Chvátal closure, Chvátal's degree-sequence theorem, pancyclicity, toughness, the travelling-salesman connection)
Dirac 1952 — Some theorems on abstract graphs · Proceedings of the London Mathematical Society (3) 2 (1952) 69-81; if δ(G) ≥ n/2 and n ≥ 3 then G is Hamiltonian
Ore 1960 — Note on Hamilton circuits · American Mathematical Monthly 67 (1960) 55; deg(u)+deg(v) ≥ n for all non-adjacent u,v implies Hamiltonian
Bondy, Chvátal 1976 — A method in graph theory · Discrete Mathematics 15 (1976) 111-135; the closure operation and the stability of Hamiltonicity under adding edges between degree-sum ≥ n non-adjacent pairs
Chvátal 1972 — On Hamilton's ideals · Journal of Combinatorial Theory Series B 12 (1972) 163-168; the best monotone degree-sequence condition for Hamiltonicity
Chvátal, Erdős 1972 — A note on Hamiltonian circuits · Discrete Mathematics 2 (1972) 111-113; κ(G) ≥ α(G) implies G Hamiltonian
Tutte 1946 — On Hamiltonian circuits · Journal of the London Mathematical Society 21 (1946) 98-101; the first planar 3-connected cubic non-Hamiltonian graph, refuting Tait's conjecture

Estimated time

beginner: 20m
intermediate: 50m
master: 90m