Chapter 5 · Euler Tours and Hamilton Cycles
When Hamiltonian Cycles Must Exist
Dirac, Ore and Pósa — sufficient degree conditions, and the rotation-extend argument behind them.
Whereas Euler's condition is exact and cheap, Hamiltonicity is NP-complete (The NP-complete Graph Problems Worth Knowing). What survives is a family of sufficient conditions of the same shape — "enough edges forces the cycle" — and all of them are proved by one argument.
If n ≥ 3 and δ(G) ≥ n/2, then G has a Hamiltonian cycle.
First, G is connected: two components would have to contain a vertex of degree ≤ n/2 - 1 by the pigeonhole principle, contradicting δ ≥ n/2.
Let P = v1 v2 … v_ℓ be a longest path (extremal choice, The Extremal Principle). Maximality puts every neighbour of v1 and of v_ℓ on P — otherwise P extends. Define
Claim 1. i ∈ S ∩ T gives a cycle through all vertices of P: re-cut the path at v1 vi+1 to get vi+1 vi … v1 vi+2 … v_ℓ, then close it with v_ℓ vi. Claim 2. ℓ = n. If not, the cycle from Claim 1 (or the edge v1 v_ℓ, which likewise closes P into a cycle on V(P)) misses some vertex; by connectedness some edge joins V(P) to a vertex outside, and cutting the cycle there yields a path on ℓ+1 vertices — contradicting the choice of P. Conclusion. Suppose no Hamiltonian cycle exists. Then v1 v_ℓ ∉ E (else P closes), so deg(v1) + deg(v_ℓ) ≥ n by δ ≥ n/2, i.e. |S| + |T| ≥ n. But S, T ⊆ {1, …, n-1} are disjoint by Claim 1, so |S| + |T| ≤ n-1. Contradiction — and the case i ∈ S ∩ T we excluded in Claim 1 is the Hamiltonian cycle. ∎
If n ≥ 3 and deg(u) + deg(v) ≥ n for every non-adjacent pair u,v, then G is Hamiltonian.
Dirac is the special case. The proof above is already the Ore proof — the only place δ ≥ n/2 was used is the bound |S| + |T| = deg(v1) + deg(v_ℓ) ≥ n, and Ore assumes exactly that for the (necessarily non-adjacent) pair {v1, v_ℓ}.
If for every k < n/2 at most k vertices have degree ≤ k, then G is Hamiltonian. Bondy–Chvátal: G is Hamiltonian ⇔ G + uv is, for non-adjacent u,v with deg(u)+deg(v) ≥ n. So "repeatedly add all such edges until nothing changes; then test Dirac" is an O(n3) decision procedure for the closure, and the closure is unique.
δ ≥ n/2 cannot be weakened: two copies of K⌈ n/2 ⌉ - 1 joined by a single edge has δ = ⌈ n/2 ⌉ - 1 and no Hamiltonian cycle (the joining edge is a bridge). This "two cliques glued at a cut edge" and its k-clique-chain relatives are the standard counterexample generators — build them whenever you doubt a bound.
Other useful guarantees
- every 4-connected planar graph is Hamiltonian (Tutte); 3-connected planar is not (Herschel graph, 11 vertices),
- every tournament with a Hamilton cycle ⇔ strongly connected (Tournaments),
- every connected vertex-transitive graph is conjectured Hamiltonian (open in general, verified for many families),
- line graphs: every 2-connected graph H has L(H) Hamiltonian unless H ≅ K3-type exceptions (Harary–Nash-Williams),
- G with κ(G) ≥ independence number α(G) is Hamiltonian (Chvátal–Erdős) — a connectivity version rather than a degree version, and often easier to verify.
- δ ≥ n/2 ⇒ G is Hamiltonian connected? — strengthen it: G has a cycle through any prescribed vertex.
- Every graph with δ ≥ 3 has a cycle of length at least δ + 1, and this is tight (show Kδ+1 joined appropriately).
- Chvátal–Erdős: longest path has at least min(n, 2δ) vertices — deduce Dirac.