Using the Minimum-Degree Test
A degree condition can certify that a graph has a Hamiltonian cycle without requiring us to search through all possible vertex orders. The key is to calculate the minimum degree, compare it with a threshold determined by the order of the graph, and apply Dirac’s theorem when its hypotheses are satisfied. The test is sufficient, not necessary: passing proves Hamiltonicity, while failing to pass does not decide the question.
All graphs in this tutorial are finite and simple. A Hamiltonian cycle is a cycle that contains every vertex of the graph exactly once before returning to its starting vertex. The order of a graph \(G\) is \(n=|V(G)|\), and its minimum degree is \(\delta(G)=\min\{\deg(v):v\in V(G)\}\). Dirac’s theorem concerns graphs of order at least \(3\).
Since degrees are integers, the condition can be checked using the integer threshold \(\lceil n/2\rceil\), the least integer greater than or equal to \(n/2\). Thus, for even order \(n=2k\), the requirement is \(\delta(G)\ge k\); for odd order \(n=2k+1\), it is \(\delta(G)\ge k+1\). In particular, when \(n\) is odd, a minimum degree of \(k\) does not meet the condition.
Confirm that \(n\ge3\). If not, Dirac’s theorem does not apply.
Find the degree of every vertex and take the minimum. Do not use the average degree in place of \(\delta(G)\).
Check whether \(\delta(G)\ge\lceil n/2\rceil\). If so, Dirac’s theorem certifies a Hamiltonian cycle.
If \(\delta(G)<\lceil n/2\rceil\), Dirac’s theorem gives no conclusion. The graph might still be Hamiltonian.
What the Test Guarantees
Proof. Since \(\lceil n/2\rceil\ge n/2\), the hypothesis implies \(\delta(G)\ge n/2\). The order and simplicity assumptions are exactly those required by Dirac’s theorem, so that theorem gives a Hamiltonian cycle in \(G\). If the inequality fails, the hypothesis of Dirac’s theorem is false, and its conditional conclusion cannot be applied. In particular, failure of the hypothesis is not a proof of the negation of the conclusion: that would require a separate argument showing that no Hamiltonian cycle exists. \(\square\)
The proposition explains why degree checking is a certificate method rather than a complete test for Hamiltonicity. A successful calculation supplies a theorem-backed guarantee. An unsuccessful calculation only tells us that this particular guarantee is unavailable; we must examine the graph further if we want to decide whether it has a Hamiltonian cycle.
Worked Example: A Graph at the Threshold
Let \(G\) be the complete bipartite graph with vertex set \(X\cup Y\), where \(X=\{x_1,x_2,x_3,x_4\}\) and \(Y=\{y_1,y_2,y_3,y_4\}\). Its edge set consists of all \(x_i y_j\) with \(1\le i\le4\) and \(1\le j\le4\); there are no edges within \(X\) or within \(Y\). Decide whether Dirac’s criterion applies.
The graph has order \(n=4+4=8\), so the threshold is \(\lceil 8/2\rceil=4\). Each \(x_i\) is adjacent to all four vertices of \(Y\), and each \(y_j\) to all four vertices of \(X\). Therefore every vertex has degree \(4\), and \(\delta(G)=4\). Since \(4\ge4\), Dirac’s theorem certifies that \(G\) is Hamiltonian.
For a direct check, the sequence \(x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4,x_1\) is a cycle: each successive pair is an edge because it has one endpoint in each part, and all eight vertices occur once before the return to \(x_1\).
Check: The edge set has \(4\cdot4=16\) edges. The degree sum is \(8\cdot4=32\), which equals \(2|E(G)|=2\cdot16=32\). This independently verifies the degree and edge counts.
Worked Example: An Odd-Order Graph That Passes
Let \(G\) have vertex set \(\{1,2,3,4,5,6,7\}\) and edge set consisting of every pair of distinct vertices except \(12,23,34,45,56,67,71\). The excluded pairs form a 7-cycle. Apply Dirac’s criterion.
There are \(7\) vertices, so \(\lceil n/2\rceil=\lceil7/2\rceil=4\). In the complete graph on these vertices, each vertex has degree \(6\). Each vertex is incident to exactly two of the seven excluded edges, so its degree in \(G\) is \(6-2=4\). Thus \(\delta(G)=4\), which meets the threshold.
Dirac’s theorem certifies Hamiltonicity. In fact, \(1,3,5,7,2,4,6,1\) is a Hamiltonian cycle. Its successive edges are \(13,35,57,72,24,46,61\); none is in the excluded list, and all seven vertices appear once before the return.
Check: The complete graph on seven vertices has \(7\cdot6/2=21\) edges. Removing the seven specified edges leaves \(21-7=14\). The degrees sum to \(7\cdot4=28\), and \(2|E(G)|=2\cdot14=28\), as required.
When the Threshold Is Not Met
A failed minimum-degree comparison is not itself a negative answer. The next two examples show both possibilities: a graph below the threshold can still be Hamiltonian, while another graph below it can fail to be Hamiltonian. In each case, the degree test has the same outcome—no Dirac certificate—but the graphs’ actual properties differ.
Worked Example: A Hamiltonian Graph Below the Threshold
Let \(G\) have vertex set \(\{1,2,3,4,5,6\}\) and edge set \(\{12,23,34,45,56,61\}\). This is the cycle \(C_6\). Its order is \(n=6\), so Dirac’s threshold is \(\lceil6/2\rceil=3\).
Each vertex is incident to two listed edges, so every degree is \(2\) and \(\delta(G)=2\). Since \(2<3\), Dirac’s theorem gives no conclusion. Nevertheless, the listed edges themselves form the Hamiltonian cycle \(1,2,3,4,5,6,1\), which contains every vertex exactly once before returning to \(1\).
Check: The graph has \(6\) edges, and its degree sum is \(6\cdot2=12=2\cdot6\). The degree calculation is consistent with the specified edge set; the explicit cycle confirms Hamiltonicity independently of Dirac’s criterion.
Worked Example: A Disconnected Graph Below the Threshold
Let \(H\) have vertex set \(\{1,2,3,4,5,6\}\) and edge set \(\{12,23,31,45,56,64\}\). It consists of two separate triangles, one on \(\{1,2,3\}\) and one on \(\{4,5,6\}\).
The order is \(6\), giving threshold \(\lceil6/2\rceil=3\). Each vertex has degree \(2\), so \(\delta(H)=2<3\), and Dirac’s criterion does not apply. This graph is not Hamiltonian: every edge has both endpoints in one of the two listed triples, so there is no edge joining the triples. A cycle that contains vertices from both triples would have to move from one triple to the other along such an edge, which is impossible.
Check: There are \(6\) edges, and the degree sum is \(6\cdot2=12=2\cdot6\). The two components are nonempty and have no edge between them, confirming directly why a cycle cannot include all six vertices.
Common Mistakes and Practical Use
Rounding the odd-order threshold down. For a graph of order \(7\), the condition is \(\delta(G)\ge7/2=3.5\). Because degree is an integer, this means \(\delta(G)\ge4\), not \(\delta(G)\ge3\). For example, let \(K_{3,4}\) have parts of sizes \(3\) and \(4\), with all edges between the parts and none within either part. Its vertices in the part of size \(3\) have degree \(4\), and its vertices in the part of size \(4\) have degree \(3\); hence \(\delta(K_{3,4})=3\). The incorrect calculation \(3\ge7/2\) would claim that the threshold is met, but \(3<3.5\), so it is not. This example is not Hamiltonian either: a cycle in a bipartite graph alternates between the two parts and therefore uses the same number of vertices from each, whereas the parts here have different sizes. The criterion’s failure, however, is not by itself the proof of that fact.
Using average degree instead of minimum degree. The theorem requires every vertex to have degree at least \(n/2\). A large average can coexist with a vertex whose degree is too small, so the average cannot replace \(\delta(G)\). Calculate the individual degrees, or otherwise establish a valid lower bound for all of them.
Treating a failed test as a disproof. The cycle \(C_6\) has \(\delta=2<3\) and is Hamiltonian, while the two-triangle graph also has \(\delta=2<3\) and is not Hamiltonian. The same failed comparison occurs in both examples. To prove non-Hamiltonicity, use a separate obstruction; to prove Hamiltonicity below Dirac’s threshold, exhibit a Hamiltonian cycle or use another valid argument.
In practice, Dirac’s criterion is especially useful when a graph is given by a sufficiently dense edge set or by a degree description that makes its minimum degree easy to establish. Its application is short, but its conclusion must be kept within the theorem’s exact hypotheses: a simple graph, order at least \(3\), and minimum degree at least half the order. Passing the test proves Hamiltonicity; missing any one of those conditions means this particular theorem supplies no certificate.
Check Your Understanding
For each question, distinguish what the degree calculation establishes from what would require an additional argument.
- A simple graph has order \(10\) and minimum degree \(5\). Does Dirac’s theorem certify that it is Hamiltonian? State the threshold.
- A simple graph has order \(9\) and minimum degree \(4\). Does it meet Dirac’s condition? Explain the integer threshold.
- Give a reason why \(\delta(G)<\lceil n/2\rceil\) does not prove that \(G\) is non-Hamiltonian.
- For the graph \(K_{3,4}\), calculate the degrees on both parts and explain why it does not meet Dirac’s condition.
- What extra information, beyond a failed Dirac test, would prove that a graph is not Hamiltonian?