Sharpness of Dirac's Minimum-Degree Bound

Why Examine Dirac’s Threshold?

Dirac’s theorem gives a sufficient condition for Hamiltonicity: if a finite simple graph has order \(n\ge 3\) and minimum degree at least \(n/2\), then it has a Hamiltonian cycle. A Hamiltonian cycle is a cycle that visits every vertex exactly once before returning to its starting vertex. The theorem does not say that every graph below the degree threshold is nonhamiltonian. To test whether the threshold can be lowered as a general guarantee, we need examples that have degree as close to \(n/2\) as possible but still have no Hamiltonian cycle.

Complete bipartite graphs provide such examples. In a complete bipartite graph, the vertices are split into two parts; every vertex in one part is adjacent to every vertex in the other, and there are no edges within either part. If the two parts have different sizes, a cycle that alternates between the parts cannot use all vertices. We will use this obstruction to measure how close a nonhamiltonian graph can come to Dirac’s degree threshold.

Because these graphs are simple, an edge between two vertices is counted once. Their order is \(a+b\), their size is \(ab\), and their minimum degree is \(\min(a,b)\). The degree formula follows directly from the definition: a vertex is adjacent to every vertex of the opposite part and to no vertex in its own part.

The Alternation Obstruction

Proof. Suppose \(K_{a,b}\) has a Hamiltonian cycle. Each edge has one endpoint in \(A\) and one in \(B\). Consequently, as we traverse the cycle, its vertices alternate between \(A\) and \(B\). Since the cycle returns to its starting vertex, its length is even; write it as \(2q\). In the alternating sequence, exactly \(q\) vertices lie in \(A\) and exactly \(q\) lie in \(B\). A Hamiltonian cycle contains every vertex, so \(a=q=b\). Therefore the two part sizes must be equal. \(\square\)

This lemma gives a direct nonhamiltonicity test for the examples below: if their part sizes differ, the lemma rules out a Hamiltonian cycle. It is not a claim that every complete bipartite graph with equal parts is Hamiltonian. In fact, when \(a=b\ge 2\), listing the vertices alternately as \(a_1,b_1,a_2,b_2,\dots,a_a,b_a\) gives a Hamiltonian cycle, since every consecutive pair, including the last and first, crosses between the parts.

The odd-order pattern is \(K_{r,r+1}\). It has order \(2r+1\), minimum degree \(r\), and one more vertex in one part than the other. The degree lies immediately below the threshold: \(n/2=r+1/2\), while the integer degree \(r\) is half a unit smaller. Dirac’s condition, for an integer-valued degree, is equivalent to \(\delta(G)\ge\lceil n/2\rceil\). When \(n=2r+1\), this requires \(\delta(G)\ge r+1\), one more than the value in this family.

Even Orders and the Integer Threshold

For an even order, the Dirac threshold is itself an integer, so the examples must have minimum degree one below that integer. Choose \(K_{r-1,r+1}\) for \(r\ge2\). Its order is \(2r\), and its minimum degree is \(r-1\), whereas the threshold is \(n/2=r\). The part sizes differ, so the graph is nonhamiltonian by the lemma. The choice of part sizes differs from the odd-order family, but the example again misses the threshold by exactly one degree.

What “Sharp” Means Here

Proof. Fix \(c\) with \(0\le c<1/2\). Since \(1-2c>0\), choose a positive integer \(r\) such that \(r>c/(1-2c)\). Let \(G=K_{r,r+1}\). Its order is \(n=2r+1\ge3\), and its minimum degree is \(r\). The choice of \(r\) implies \(r(1-2c)>c\), hence \(r>2cr+c=c(2r+1)=cn\). Therefore \(\delta(G)=r>cn\). Its parts have unequal sizes, so the lemma proves that \(G\) is nonhamiltonian. The ratio also satisfies \(r/(2r+1)=1/2-1/(4r+2)\), which approaches \(1/2\) as \(r\) increases. Thus counterexamples can have minimum-degree ratios arbitrarily close to one half from below. \(\square\)

The theorem specifies the sense in which Dirac’s constant is sharp: no fixed fraction strictly below one half can replace it as a universal guarantee. The examples do not say that a graph with degree below \(n/2\) must fail to be Hamiltonian; they only show that minimum degree alone cannot guarantee Hamiltonicity at every lower fixed fraction.

Common Mistake: Using the Wrong Part’s Degree

In \(K_{a,b}\), a vertex in the part of size \(a\) has degree \(b\), not \(a\). For example, in \(K_{4,5}\), a tempting but incorrect calculation is to say that vertices in the part of size \(5\) have degree \(5\), and hence \(\delta=5\). Those vertices are adjacent to the four vertices in the other part, so their degree is \(4\); vertices in the part of size \(4\) have degree \(5\). The corrected minimum is \(\delta=\min(4,5)=4\), which is below \(n/2=9/2\). Check the degree sum: \(4\cdot5+5\cdot4=40=2\cdot20\), where \(20=4\cdot5\) is the edge count. This independent count confirms the corrected degrees.

A second point of care is the direction of the conclusion. Dirac’s theorem says that meeting its degree condition is sufficient for a Hamiltonian cycle. A nonhamiltonian graph just below the condition demonstrates sharpness of the bound; it does not turn the sufficient condition into an “if and only if” characterization.