Choosing a Test for Hamiltonicity
A graph may satisfy several sufficient conditions for having a Hamiltonian cycle, and the practical question is which condition to check first. Some tests require only the minimum degree; others use every nonedge, the whole degree sequence, or structural parameters such as vertex connectivity and independence number. An efficient approach starts with the cheapest calculation and moves to more detailed tests when needed.
All graphs considered here are finite and simple. A Hamiltonian cycle is a cycle containing every vertex of the graph. The order of \(G\) is \(n=|V(G)|\), and its minimum degree is \(\delta(G)\). A nonedge is a pair of distinct vertices that are not adjacent. The degree sequence is written in nondecreasing order as \(d_1\le d_2\le\cdots\le d_n\). An independent set is a set of pairwise nonadjacent vertices, and \(\alpha(G)\) is the largest size of one. The vertex connectivity \(\kappa(G)\) is the minimum number of vertices whose deletion disconnects the graph or leaves at most one vertex; for a complete graph \(K_n\), set \(\kappa(K_n)=n-1\).
The Four Conditions to Compare
- Dirac’s condition: if \(\delta(G)\ge n/2\), then \(G\) is Hamiltonian.
- Ore’s condition: if \(\deg(u)+\deg(v)\ge n\) for every nonedge \(uv\), then \(G\) is Hamiltonian.
- Chvatal’s degree-sequence condition: if, for every integer \(k\) with \(1\le k<n/2\), either \(d_k>k\) or \(d_{n-k}\ge n-k\), then \(G\) is Hamiltonian.
- The Chvatal–Erdos condition: if \(\kappa(G)\ge\alpha(G)\), then \(G\) is Hamiltonian.
These conditions use different summaries of a graph. Dirac’s test is usually quickest: find the smallest degree and compare it with half the order. Ore’s test needs degree sums only for nonedges, not for edges. Chvatal’s test uses the sorted degree sequence, but its alternatives must be checked at every index in the stated range. The Chvatal–Erdos test can be useful when connectivity and independent sets are easier to assess than all nonedges.
Dirac’s condition always implies Ore’s condition. This relationship helps explain why the minimum-degree calculation is a natural first step.
Proof. Assume \(\delta(G)\ge n/2\). Let \(uv\) be any nonedge. By the definition of minimum degree, \(\deg(u)\ge\delta(G)\) and \(\deg(v)\ge\delta(G)\). Therefore \(\deg(u)+\deg(v)\ge2\delta(G)\ge n\). This holds for every nonedge, so Ore’s condition holds. \(\square\)
The implication goes only in this direction as stated: passing Dirac’s test guarantees that Ore’s degree-sum hypothesis also holds, but a graph can fail Dirac’s test and still pass Ore’s. More generally, the tests are sufficient certificates. A test that fails has not established that the graph lacks a Hamiltonian cycle.
A Practical Order of Checks
Compute \(n\), all vertex degrees, and \(\delta(G)\). If \(\delta(G)\ge n/2\), Dirac’s theorem certifies Hamiltonicity.
For each nonedge \(uv\), calculate \(\deg(u)+\deg(v)\). Ore’s theorem applies only if every such sum is at least \(n\). If there are no nonedges, this universal condition holds vacuously.
For each integer \(k\) with \(1\le k<n/2\), test the two alternatives \(d_k>k\) and \(d_{n-k}\ge n-k\). The condition requires at least one alternative at every such \(k\).
Compute \(\kappa(G)\) and \(\alpha(G)\). If \(\kappa(G)\ge\alpha(G)\), the Chvatal–Erdos theorem certifies Hamiltonicity.
This is a menu, not a ranking in which each test is always harder than the one before it. The graph’s representation and structure matter. For example, a graph described by a degree sequence may invite Chvatal’s test immediately, while a graph with an obvious small vertex cut and a readily identified independent set may make the Chvatal–Erdos comparison convenient.
Worked Example: Dirac’s Test on a Complete Bipartite Graph
Let \(G=K_{3,3}\), with parts \(X=\{a,b,c\}\) and \(Y=\{x,y,z\}\), and edge set \(E=\{ax,ay,az,bx,by,bz,cx,cy,cz\}\). Thus \(n=6\). Each vertex is adjacent to all three vertices in the opposite part, so every degree is \(3\), and \(\delta(G)=3\).
Dirac’s threshold is \(n/2=6/2=3\). Since \(\delta(G)=3\ge3\), Dirac’s theorem applies and guarantees a Hamiltonian cycle. Ore’s condition also holds: every nonedge is within one of the two parts, and both its endpoints have degree \(3\), so its degree sum is \(3+3=6=n\).
For a direct check of the conclusion, \(a,x,b,y,c,z,a\) is a cycle: its six edges are \(ax,xb,by,yc,cz,za\), all of which belong to \(E\), and it visits all six vertices exactly once before returning to \(a\). Independently, the graph has \(3\cdot3=9\) edges because each of the three vertices in \(X\) is joined to all three vertices in \(Y\); the listed edge set also has nine edges.
When the Degree-Sequence Test Adds Information
Dirac’s test compresses all degrees to the minimum, while Chvatal’s test uses selected positions in the sorted sequence. Its alternatives are an “or” at each index, not an “and”: for a given \(k\), it is enough that \(d_k>k\) or \(d_{n-k}\ge n-k\). However, the condition must pass at every eligible index \(k\).
Worked Example: Chvatal’s Condition Passes When Dirac’s Does Not
Take \(V=\{a,b,c,d,e,f\}\) and \(E=\{ad,ae,bd,be,bf,cd,ce,cf,df,ef\}\). The degrees, computed from these incident edges, are \(\deg(a)=2\), \(\deg(b)=3\), \(\deg(c)=3\), \(\deg(d)=4\), \(\deg(e)=4\), and \(\deg(f)=4\). Thus \(n=6\), \(\delta(G)=2\), and the degree sequence is \(2,3,3,4,4,4\).
Dirac’s threshold is \(n/2=6/2=3\), so Dirac’s condition fails because \(2<3\). Ore’s condition also fails: \(ab\) is a nonedge, and \(\deg(a)+\deg(b)=2+3=5<6=n\).
For Chvatal’s condition the eligible integers satisfy \(1\le k<6/2=3\), so \(k=1,2\). At \(k=1\), \(d_1=2>1\). At \(k=2\), \(d_2=3>2\). One alternative already holds at each eligible index, so Chvatal’s condition applies and certifies Hamiltonicity.
Check: the cycle \(a,d,b,f,c,e,a\) uses the edges \(ad,db,bf,fc,ce,ea\), each listed in \(E\), and visits all six vertices once. The degree sum is \(2+3+3+4+4+4=20\); independently, the ten listed edges contribute \(2\) to the sum of degrees each, giving \(2|E|=2\cdot10=20\).
The example illustrates why the degree sequence can be a useful next check: the minimum degree alone does not meet Dirac’s threshold, and a single nonedge disproves Ore’s hypothesis, but the degree-sequence condition still applies. A failed test does not interfere with applying a different test; each theorem has its own hypothesis.
When Connectivity and Independence Are Easier to Use
The Chvatal–Erdos condition compares \(\kappa(G)\) with \(\alpha(G)\). Connectivity is a vertex-removal quantity, whereas independence number asks for the largest set with no internal edges. Neither is obtained just by reading off the minimum degree. When using this criterion, be sure to calculate the parameters themselves rather than substituting a degree-based guess.
Worked Example: The Chvatal–Erdos Test on a Squared Cycle
Use vertices \(V=\{0,1,\ldots,9\}\), with subscripts interpreted modulo \(10\), and edge set \(E=\{i(i+1),i(i+2):i\in\{0,1,\ldots,9\}\}\). This is the graph in which two vertices are adjacent when their cyclic distance is \(1\) or \(2\). Each vertex \(i\) has exactly the four neighbors \(i-2,i-1,i+1,i+2\), so \(n=10\), the degree sequence consists of ten \(4\)s, and \(\delta(G)=4\).
Dirac’s threshold is \(10/2=5\), so Dirac’s condition fails because \(4<5\). The pair \(0,3\) is a nonedge, since its cyclic distance is \(3\), and its degree sum is \(4+4=8<10\); hence Ore’s condition fails. For Chvatal’s condition the indices are \(k=1,2,3,4\). For \(k=1,2,3\), \(d_k=4>k\). At \(k=4\), \(d_4=4\) is not greater than \(4\), and \(d_{10-4}=d_6=4<6=10-4\). Thus the condition fails at \(k=4\).
We now calculate the two parameters needed for Chvatal–Erdos. First, \(\alpha(G)=3\). If \(r\) vertices form an independent set, the cyclic gaps between successive chosen vertices must each be at least \(3\), because vertices at cyclic distance \(1\) or \(2\) are adjacent. The gaps sum to \(10\), so \(3r\le10\), which gives \(r\le3\). The set \(\{0,3,6\}\) is independent: its successive cyclic gaps are \(3,3,4\), so every pair has cyclic distance at least \(3\). Therefore \(\alpha(G)=3\).
Next, \(\kappa(G)=4\). Deleting the four neighbors \(\{8,9,1,2\}\) of \(0\) leaves \(0\) isolated and leaves the other vertices \(\{3,4,5,6,7\}\) connected by the edges \(34,45,56,67\). The remaining graph is disconnected, so \(\kappa(G)\le4\). Conversely, deleting at most three vertices cannot disconnect the graph. In the cyclic order of the remaining vertices, a gap between consecutive remaining vertices must contain at least two deleted vertices if those two vertices are in different components: with no deleted vertex they are adjacent at distance \(1\), and with just one they are adjacent at distance \(2\). If the remaining graph had at least two components, there would be at least two changes of component around the cyclic order, requiring at least four deleted vertices. This contradicts deletion of at most three. Thus \(\kappa(G)\ge4\), and \(\kappa(G)=4\).
Since \(\kappa(G)=4\ge3=\alpha(G)\), the Chvatal–Erdos condition certifies that \(G\) is Hamiltonian. The cycle \(0,1,2,3,4,5,6,7,8,9,0\) provides a direct check: every consecutive pair has cyclic distance \(1\), and all ten vertices occur once. The edge set has \(20\) distinct edges: the ten edges of cyclic distance \(1\) and ten of cyclic distance \(2\). This agrees with the degree count, since \(10\cdot4=40=2|E|\).
Common Mistakes and a Reliable Conclusion
Using the wrong quantifier in Ore’s condition. A common incorrect calculation checks only one nonedge and concludes that Ore’s condition holds because its degree sum is large enough. For example, in \(K_{3,3}\), checking \(ax\) gives \(3+3=6\), but that pair is an edge, not a nonedge. The correction is to identify nonedges and verify the bound for every one; in \(K_{3,3}\), every nonedge lies within a part and has degree sum \(6\).
Stopping the Chvatal check at the first successful index. The degree-sequence condition is a requirement at every \(k\) in its range. In the squared-cycle example, the tests at \(k=1,2,3\) pass, but \(k=4\) fails: \(d_4=4\) is not greater than \(4\), and \(d_6=4\) is less than \(6\). That is enough to show that this particular sufficient condition does not apply.
A good conclusion reports exactly what was established: name the criterion whose full hypothesis holds and state that it guarantees a Hamiltonian cycle. If none of the tested criteria applies, the calculation is inconclusive about Hamiltonicity; another argument or method would be needed to settle the graph.
Check Your Understanding
For each question, state the calculation that supports your conclusion.
- For a graph of order \(8\) with minimum degree \(4\), which of Dirac’s and Ore’s conditions can be certified from this information alone?
- A graph of order \(7\) has degree sequence \(2,3,3,4,4,5,5\). Check Chvatal’s condition at every eligible index.
- Explain why one nonedge with degree sum less than \(n\) disproves Ore’s hypothesis, while one nonedge with sum at least \(n\) does not establish it.
- For the graph in the squared-cycle example, list the four neighbors of vertex \(5\) and confirm its degree.
- If all four sufficient conditions fail to apply to a graph, what conclusion about the existence of a Hamiltonian cycle is justified by these tests?