---
title: "When Hamiltonian Cycles Must Exist"
summary: Dirac, Ore and Pósa — sufficient degree conditions, and the rotation-extend argument behind them.
difficulty: olympiad
tags: [hamilton, existence, olympiad]
see: [euler/hamilton-dp, proofs/extremal, special/independent]
---

Whereas Euler's condition is *exact* and cheap, Hamiltonicity is NP-complete (@complexity/npc-graphs). 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.

:::theorem title="Dirac (1952)"
If $n \ge 3$ and $\delta(G) \ge n/2$, then $G$ has a Hamiltonian cycle.
:::

:::proof
First, $G$ is connected: two components would have to contain a vertex of degree $\le n/2 - 1$ by the pigeonhole principle, contradicting $\delta \ge n/2$.

Let $P = v_1 v_2 \dots v_\ell$ be a **longest path** (extremal choice, @proofs/extremal). Maximality puts every neighbour of $v_1$ and of $v_\ell$ on $P$ — otherwise $P$ extends. Define
$$S = \{i \le \ell-1 : v_1 v_{i+1} \in E\}, \qquad T = \{i \le \ell-1 : v_\ell v_i \in E\}.$$
*Claim 1.* $i \in S \cap T$ gives a cycle through all vertices of $P$: re-cut the path at $v_1 v_{i+1}$ to get $v_{i+1} v_i \dots v_1 v_{i+2} \dots v_\ell$, then close it with $v_\ell v_i$.
*Claim 2.* $\ell = n$. If not, the cycle from Claim 1 (or the edge $v_1 v_\ell$, 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 $\ell+1$ vertices — contradicting the choice of $P$.
*Conclusion.* Suppose no Hamiltonian cycle exists. Then $v_1 v_\ell \notin E$ (else $P$ closes), so $\deg(v_1) + \deg(v_\ell) \ge n$ by $\delta \ge n/2$, i.e. $|S| + |T| \ge n$. But $S, T \subseteq \{1, \dots, n-1\}$ are disjoint by Claim 1, so $|S| + |T| \le n-1$. Contradiction — and the case $i \in S \cap T$ we excluded in Claim 1 *is* the Hamiltonian cycle. ∎
:::

:::theorem title="Ore (1960) — the stronger, easier-to-apply form"
If $n \ge 3$ and $\deg(u) + \deg(v) \ge 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 $\delta \ge n/2$ was used is the bound $|S| + |T| = \deg(v_1) + \deg(v_\ell) \ge n$, and Ore assumes exactly that for the (necessarily non-adjacent) pair $\{v_1, v_\ell\}$.

:::theorem title="Pósa (and the closure theorem)"
If for every $k < n/2$ at most $k$ vertices have degree $\le k$, then $G$ is Hamiltonian. Bondy–Chvátal: $G$ is Hamiltonian $\iff$ $G + uv$ is, for non-adjacent $u,v$ with $\deg(u)+\deg(v) \ge n$. So "repeatedly add all such edges until nothing changes; then test Dirac" is an $O(n^3)$ decision *procedure* for the closure, and the closure is unique.
:::

:::note title="Necessity: how sharp are these?"
$\delta \ge n/2$ cannot be weakened: two copies of $K_{\lceil n/2 \rceil - 1}$ joined by a single edge has $\delta = \lceil n/2 \rceil - 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.
:::

:::props title="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 (@directed/tournament),
- 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 \cong K_3$-type exceptions (Harary–Nash-Williams),
- $G$ with $\kappa(G) \ge$ independence number $\alpha(G)$ is Hamiltonian (Chvátal–Erdős) — a connectivity version rather than a degree version, and often easier to verify.
:::

:::figure src="Ore_Theorem_Proof.svg" caption="The rotation picture: $v_1$ reaches $v_{i+1}$, $v_\ell$ reaches $v_i$, and re-cutting the path at that pair turns a longest path into a cycle."
:::

:::exercise title="Prove these three (each is the same argument with one twist)"
1. $\delta \ge n/2 \Rightarrow$ $G$ is Hamiltonian *connected*? — strengthen it: $G$ has a cycle through any prescribed vertex.
2. Every graph with $\delta \ge 3$ has a cycle of length at least $\delta + 1$, and this is tight (show $K_{\delta+1}$ joined appropriately).
3. Chvátal–Erdős: longest path has at least $\min(n, 2\delta)$ vertices — deduce Dirac.
:::