Dirac and Ore Theorems

Unlike Eulerian circuits which have a simple necessary and sufficient condition, Hamiltonian cycles have no known complete characterization. However, several sufficient conditions based on vertex degrees guarantee Hamiltonicity.

TheoremDirac's Theorem (1952)

Let $G$ be a graph with $n \geq 3$ vertices. If every vertex has degree at least $n/2$ , then $G$ is Hamiltonian.

$\delta(G) \geq n/2 \implies G \text{ is Hamiltonian}$

where $\delta(G) = \min_{v \in V} \deg(v)$ is the minimum degree.

Proof

Suppose $G$ satisfies the degree condition but is not Hamiltonian. Among all non-Hamiltonian graphs satisfying the condition, let $G$ be one with the maximum number of edges.

Since $G$ is not Hamiltonian but adding any edge creates a Hamiltonian cycle, $G$ must have a Hamiltonian path $P = v_1, v_2, \ldots, v_n$ .

Consider vertices adjacent to $v_1$ and $v_n$ . Let $S = \{i : v_1 v_i \in E\}$ and $T = \{i : v_{i+1} v_n \in E\}$ (indices where $v_1$ has an edge to $v_i$ and $v_n$ has an edge from $v_i$ 's predecessor).

Since $|S| = \deg(v_1) \geq n/2$ and $|T| = \deg(v_n) \geq n/2$ , by pigeonhole principle, $S \cap T \neq \emptyset$ . Let $j \in S \cap T$ .

Then we can form a cycle: $v_1, v_2, \ldots, v_j, v_n, v_{n-1}, \ldots, v_{j+1}, v_1$ . This is a Hamiltonian cycle, contradicting our assumption.

■

TheoremOre's Theorem (1960)

Let $G$ be a graph with $n \geq 3$ vertices. If for every pair of non-adjacent vertices $u,v$ , we have $\deg(u) + \deg(v) \geq n$ , then $G$ is Hamiltonian.

$\text{For all } u,v \notin E: \deg(u) + \deg(v) \geq n \implies G \text{ is Hamiltonian}$

Ore's theorem generalizes Dirac's: if $\delta(G) \geq n/2$ , then for any non-adjacent $u,v$ , we have $\deg(u) + \deg(v) \geq n$ .

Proof

Similar to Dirac's proof. Consider a non-Hamiltonian $G$ with maximum edges satisfying Ore's condition. It has a Hamiltonian path $v_1, \ldots, v_n$ .

The key insight remains: if $v_1 v_j \in E$ and $v_{j-1} v_n \in E$ for some $j$ , we can close the path into a cycle. The degree sum condition $\deg(v_1) + \deg(v_n) \geq n$ ensures such an index exists, using a counting argument on path positions.

■

ExampleSharpness of Dirac's Theorem

Consider the complete bipartite graph $K_{n/2, n/2}$ for even $n \geq 4$ . Every vertex has degree exactly $n/2$ , satisfying Dirac's condition with equality. This graph is Hamiltonian: alternate between the two parts.

However, $K_{n/2-1, n/2+1}$ has minimum degree $n/2-1 < n/2$ and is also Hamiltonian, showing Dirac's condition is sufficient but not necessary. The threshold $n/2$ is sharp: graphs with $\delta(G) = n/2 - 1$ can be non-Hamiltonian (e.g., $K_{n/2-1} \cup K_{n/2+1}$ , two disjoint cliques).

Remark

Bondy-Chvátal Theorem generalizes both results: the closure of $G$ (adding edges between non-adjacent vertices with degree sum $\geq n$ ) preserves Hamiltonicity. If the closure is complete, $G$ is Hamiltonian. This provides a polynomial-time test for graphs where the closure becomes complete.

DefinitionPósa's Lemma

A related result: if $G$ has $n$ vertices and vertex degrees satisfy $d_1 \leq d_2 \leq \cdots \leq d_n$ with $d_i \geq i+1$ for all $i < n/2$ , then $G$ is Hamiltonian. This refines Dirac's condition using the degree sequence rather than just minimum degree.

These theorems demonstrate that sufficient density (measured by degrees or edge count) implies Hamiltonicity, though the exact threshold remains a rich area of extremal graph theory.