Dirac’s Minimum-Degree Condition
A Hamiltonian cycle visits every vertex of a graph exactly once before returning to its starting vertex. Finding one can be difficult: even a graph with many edges need not have such a cycle. Dirac’s theorem gives a useful sufficient condition that can be checked using only the order and minimum degree of the graph.
Throughout, graphs are finite and simple: they have no loops or multiple edges. The order of \(G\) is \(n=|V(G)|\), and the minimum degree is \(\delta(G)=\min\{\deg(v):v\in V(G)\}\). A Hamiltonian cycle is a cycle containing every vertex of the graph. In particular, its vertices are distinct except for the repeated starting vertex at the end.
The lower bound \(n/2\) need not be an integer. Since \(\delta(G)\) is an integer, the hypothesis is equivalently \(\delta(G)\ge\lceil n/2\rceil\), where \(\lceil x\rceil\) is the least integer greater than or equal to \(x\). For even order \(n=2k\), the threshold is \(k\); for odd order \(n=2k+1\), it is \(k+1\). This difference matters when testing a graph: a minimum degree of \(k\) meets the threshold at order \(2k\), but not at order \(2k+1\).
Proof. If \(\delta(G)\ge n/2\), then \(\delta(G)\) is an integer at least \(n/2\), so it is at least the least integer greater than or equal to \(n/2\), namely \(\lceil n/2\rceil\). Conversely, \(\lceil n/2\rceil\ge n/2\), so \(\delta(G)\ge\lceil n/2\rceil\) implies \(\delta(G)\ge n/2\). \(\square\)
What the Hypothesis Tells Us
The degree bound is strong. In a simple graph on \(n\) vertices, a vertex can have at most \(n-1\) neighbors; Dirac’s condition requires every vertex to have at least about half of the other vertices as neighbors. The conclusion is global: there is one cycle that includes all vertices, not merely a collection of smaller cycles.
The hypothesis also forces the graph to be connected. This is a useful consequence to understand, although the theorem’s conclusion is stronger: a Hamiltonian cycle itself makes the graph connected.
Proof. Suppose instead that \(G\) is disconnected. Each of its connected components contains at least one vertex. A vertex in a component of order \(s\) can have at most \(s-1\) neighbors, so \(s\ge\delta(G)+1\). There are at least two components, and therefore \(n\ge2(\delta(G)+1)\). But \(\delta(G)\ge n/2\) gives \(2(\delta(G)+1)\ge n+2\), contradicting \(n\ge2(\delta(G)+1)\). Hence \(G\) is connected. \(\square\)
Worked Example: The Threshold at Even Order
Let \(G\) have vertex set \(V(G)=\{1,2,3,4\}\) and edge set \(E(G)=\{12,23,34,41\}\). Compute the minimum degree, test Dirac’s condition, and verify the conclusion.
The neighbors of \(1\) are \(2,4\), so \(\deg(1)=2\). The neighbors of \(2\) are \(1,3\), so \(\deg(2)=2\). The neighbors of \(3\) are \(2,4\), so \(\deg(3)=2\). The neighbors of \(4\) are \(1,3\), so \(\deg(4)=2\). Thus \(\delta(G)=2\), while \(n=4\) and \(n/2=4/2=2\). The hypothesis holds with equality.
The vertex sequence \(1,2,3,4,1\) is a cycle: its consecutive pairs correspond to edges \(12,23,34,41\), and the vertices \(1,2,3,4\) are distinct before the return to \(1\). It includes all four vertices, so it is Hamiltonian.
Check: the four listed edges are exactly the four edges used by that cycle, and every vertex has degree \(2\). Hence the computed minimum degree and the displayed Hamiltonian cycle agree with the theorem’s hypothesis and conclusion.
Worked Example: An Odd-Order Graph That Meets the Bound
Let \(G\) have vertex set \(V(G)=\{1,2,3,4,5\}\) and edge set \(E(G)=\{13,14,15,23,24,25,35,45\}\). This is the complete graph on these five vertices with edges \(12\) and \(34\) omitted. Test Dirac’s condition and find a Hamiltonian cycle.
Vertex \(1\) is adjacent to \(3,4,5\), so \(\deg(1)=3\). Vertex \(2\) is adjacent to \(3,4,5\), so \(\deg(2)=3\). Vertex \(3\) is adjacent to \(1,2,5\), so \(\deg(3)=3\). Vertex \(4\) is adjacent to \(1,2,5\), so \(\deg(4)=3\). Vertex \(5\) is adjacent to \(1,2,3,4\), so \(\deg(5)=4\). Therefore \(\delta(G)=3\). Here \(n=5\), so \(n/2=5/2=2.5\) and \(\lceil n/2\rceil=3\). The hypothesis holds.
The cycle \(1,3,2,4,5,1\) uses edges \(13,32,24,45,51\), all of which belong to the stated edge set. Its first five vertices are distinct, and they are exactly the vertices of \(G\). It is therefore Hamiltonian.
Check: the degrees sum to \(3+3+3+3+4=16\), which is twice the number of edges, \(2\cdot8=16\). This independently checks the degree calculation. The displayed cycle uses five distinct edges and visits all five vertices once before closing.
Sufficiency Is Not Necessity
Dirac’s theorem says that meeting the degree bound guarantees a Hamiltonian cycle. It does not say that every graph with a Hamiltonian cycle meets the bound. A graph that fails the hypothesis is not thereby shown to have no Hamiltonian cycle; the theorem simply gives no conclusion in that case.
Worked Example: A Hamiltonian Graph Below the Threshold
Let \(G\) have vertex set \(V(G)=\{1,2,3,4,5\}\) and edge set \(E(G)=\{12,23,34,45,51\}\). Find its minimum degree, check whether Dirac’s hypothesis holds, and decide whether \(G\) is Hamiltonian.
Each vertex has two neighbors: \(1\) is adjacent to \(2,5\); \(2\) to \(1,3\); \(3\) to \(2,4\); \(4\) to \(3,5\); and \(5\) to \(4,1\). Hence the five degrees are \(2,2,2,2,2\), and \(\delta(G)=2\). Since \(n=5\), the required integer threshold is \(\lceil5/2\rceil=3\). Thus \(2<3\), so Dirac’s hypothesis fails.
Nevertheless, the sequence \(1,2,3,4,5,1\) uses the edges \(12,23,34,45,51\) and visits all five distinct vertices before returning to \(1\). It is a Hamiltonian cycle. This example shows that the degree condition is sufficient but not necessary.
Check: the graph has exactly five listed edges, and the displayed cycle uses all five. Every vertex appears once among the first five terms, so the cycle is Hamiltonian even though the minimum degree is below the threshold.
Worked Example: Failure of the Bound and Failure of Hamiltonicity
Let \(G\) have vertex set \(V(G)=\{0,1,2,3,4\}\) and edge set \(E(G)=\{01,02,03,04\}\), the star \(K_{1,4}\). Compute the degrees and determine whether \(G\) can have a Hamiltonian cycle.
The center \(0\) is adjacent to all four other vertices, so \(\deg(0)=4\). Each of \(1,2,3,4\) is adjacent only to \(0\), so each has degree \(1\). Thus \(\delta(G)=1\), whereas \(n=5\) gives the threshold \(\lceil5/2\rceil=3\). Dirac’s hypothesis fails.
The graph has no Hamiltonian cycle. In any cycle, every vertex on the cycle has two distinct neighbors along that cycle. A Hamiltonian cycle would include every vertex, so every vertex would need degree at least \(2\) in \(G\). But vertices \(1,2,3,4\) each have degree \(1\). Therefore no Hamiltonian cycle exists.
Check: the edge list contains four edges, one incident to each leaf and all incident to \(0\). Each leaf has only one possible neighbor, so it cannot have the two distinct cycle neighbors required in a Hamiltonian cycle.
Using Dirac’s Theorem Carefully
A reliable application separates the hypothesis check from the conclusion. First confirm that the graph is simple and that \(n\ge3\). Next calculate each vertex degree, or use a verified degree list to find \(\delta(G)\). Compare that minimum with \(\lceil n/2\rceil\). If it meets the threshold, Dirac’s theorem guarantees a Hamiltonian cycle; unless the cycle is also required explicitly, the theorem need not provide its vertices in order. If it falls below the threshold, stop short of declaring the graph non-Hamiltonian: use another argument or exhibit a Hamiltonian cycle.
The restriction \(n\ge3\) is part of the theorem. It ensures the setting is one in which a cycle, as defined here, can exist. The condition is not a claim about graphs of order one or two, so those cases should not be inserted into the theorem by ignoring its stated hypothesis.
Common mistake: for a graph of order \(5\), one might incorrectly compare \(\delta(G)\) with \(2\), by rounding \(5/2=2.5\) down. That would wrongly treat minimum degree \(2\) as sufficient. The condition is \(\delta(G)\ge5/2\); because degree is integer, this means \(\delta(G)\ge3\), not \(\delta(G)\ge2\). The five-cycle example has minimum degree \(2\): it is Hamiltonian, but it does not satisfy Dirac’s hypothesis.
Dirac’s condition is valuable because it turns a question about a cycle through all vertices into a simple numerical test. Its strength also explains why failing the test is inconclusive: the theorem covers graphs above a threshold, while Hamiltonian graphs can lie below it. Always report both the computed minimum degree and the threshold, then state precisely whether the theorem applies.
Check Your Understanding
For each question, distinguish carefully between meeting the hypothesis and establishing the existence of a Hamiltonian cycle by some other argument.
- A graph has order \(8\) and minimum degree \(4\). Does it satisfy Dirac’s hypothesis? State the threshold.
- A graph has order \(7\) and minimum degree \(3\). Does Dirac’s theorem guarantee a Hamiltonian cycle? Explain using the integer threshold.
- Why does the five-cycle satisfy the conclusion of Dirac’s theorem without satisfying its hypothesis?
- Prove that if a graph has a Hamiltonian cycle, then every vertex has degree at least \(2\).
- For the star \(K_{1,4}\), identify its order and minimum degree, and explain why the failed Dirac hypothesis alone would not prove that it is non-Hamiltonian.