Chvatal's Degree-Sequence Condition

From Degrees to a Hamiltonicity Test

A Hamiltonian cycle visits every vertex exactly once before returning to its starting vertex. Finding one directly can require searching through many possible vertex orders. Chvatal’s degree-sequence condition offers a different approach: sort the degrees, then compare a low-degree entry with a corresponding high-degree entry. If all the required comparisons pass, the graph is guaranteed to have a Hamiltonian cycle.

All graphs in this tutorial are finite and simple. For a graph \(G=(V,E)\) of order \(n=|V|\), write its vertex degrees in nondecreasing order as \(d_1\le d_2\le\cdots\le d_n\). These are the degrees of the vertices, listed with repetitions. The test concerns this ordered list, not the labels of the vertices.

Definition: For an integer \(k\) with \(1\le k<n/2\), the paired inequality in Chvatal’s condition is the implication \(d_k\le k\ \Longrightarrow\ d_{n-k}\ge n-k\). The degree sequence satisfies the condition if this implication holds for every such \(k\).

The index bound is strict: only integers \(k<n/2\) are tested. Thus the relevant indices are \(1,\ldots,\lfloor(n-1)/2\rfloor\). The antecedent \(d_k\le k\) matters: if it is false, that index passes without requiring a comparison with \(d_{n-k}\). If it is true, the degree near the opposite end of the sequence must meet the threshold \(n-k\).

Chvatal’s Theorem

Theorem (Chvatal): Let \(G\) be a simple graph of order \(n\ge3\), with degree sequence \(d_1\le\cdots\le d_n\). If, for every integer \(k\) with \(1\le k<n/2\), \(d_k\le k\) implies \(d_{n-k}\ge n-k\), then \(G\) has a Hamiltonian cycle.

This is a sufficient condition: when the inequalities pass, Hamiltonicity follows. The converse is not asserted. A Hamiltonian graph can fail the condition, so failure of the test does not prove that the graph has no Hamiltonian cycle. The theorem’s proof is supplied in the later treatment of Chvatal’s theorem; here the focus is the exact statement and how to check it.

There is a useful way to record a failure. Since degrees are integers, the implication at a particular \(k\) fails exactly when both \(d_k\le k\) and \(d_{n-k}<n-k\). Equivalently, the paired entries satisfy \(d_k\le k\) and \(d_{n-k}\le n-k-1\).

Proposition: The degree sequence fails Chvatal’s condition if and only if there is at least one integer \(k\) with \(1\le k<n/2\) for which \(d_k\le k\) and \(d_{n-k}\le n-k-1\).

Proof. By definition, the condition fails if and only if at least one of its implications is false. An implication \(P\Longrightarrow Q\) is false exactly when \(P\) is true and \(Q\) is false. Here \(P\) is \(d_k\le k\), and \(Q\) is \(d_{n-k}\ge n-k\). As \(d_{n-k}\) is an integer, the negation of \(d_{n-k}\ge n-k\) is \(d_{n-k}\le n-k-1\). Combining these statements gives the claimed pair of inequalities, and each such pair makes the corresponding implication false. \(\square\)

How to Check the Paired Inequalities

First sort all vertex degrees, retaining repeated values. Next list only the allowed indices. At each index, test \(d_k\le k\). If it holds, compare \(d_{n-k}\) with \(n-k\); if it does not, move on. This is a check of the graph’s degree sequence, not a way to construct a Hamiltonian cycle.

Sort the degrees.
Write \(d_1\le\cdots\le d_n\), including every vertex degree exactly once.

Determine the index range.
Use exactly the integers \(k\) satisfying \(1\le k<n/2\).

Test each antecedent.
If \(d_k>k\), that index passes automatically. If \(d_k\le k\), check the paired entry \(d_{n-k}\).

Reach the correct conclusion.
If every index passes, the theorem guarantees a Hamiltonian cycle. If any index fails, the criterion gives no conclusion about whether one exists.

Worked Example: A Passing Test with an Active Index

Let \(G\) have vertex set \(\{u,v,a,b,c,d,e,f\}\). The vertices \(a,b,c,d,e,f\) induce a complete graph, and the remaining edges are \(ua,ub,va,vc\). Thus the edge set consists of the 15 pairs within \(\{a,b,c,d,e,f\}\), together with those four listed edges.

The six vertices in the complete subgraph each have degree \(5\) before the four extra edges are counted. Vertex \(a\) gains two edges, \(b\) gains one, and \(c\) gains one. Therefore \(d(a)=7\), \(d(b)=6\), \(d(c)=6\), and \(d(d)=d(e)=d(f)=5\). The vertices \(u,v\) each have degree \(2\). The sorted sequence is \(2,2,5,5,5,6,6,7\).

Here \(n=8\), so the allowed indices are \(k=1,2,3\). At \(k=1\), \(d_1=2>1\), so the antecedent is false. At \(k=2\), \(d_2=2\le2\), so check \(d_{8-2}=d_6=6\); the required inequality is \(6\ge8-2=6\), which holds. At \(k=3\), \(d_3=5>3\), so the antecedent is false. Every index passes, and Chvatal’s theorem guarantees Hamiltonicity.

Check: The graph has \(15+4=19\) edges. Its degree sum is \(2+2+5+5+5+6+6+7=38=2\cdot19\). A Hamiltonian cycle can also be exhibited directly: \(u,b,d,e,f,c,v,a,u\). Each consecutive pair is an edge, the eight vertices before the return are distinct, and they include every vertex.

Worked Example: A Hamiltonian Graph That Fails the Test

Let \(G\) have vertex set \(\{1,2,3,4,5,6\}\) and edge set \(\{12,23,34,45,56,61,13\}\). The cycle edges give each vertex degree \(2\); the additional edge \(13\) raises the degrees of \(1\) and \(3\) to \(3\). Thus the sorted degree sequence is \(2,2,2,2,3,3\).

For \(n=6\), the allowed indices are \(k=1,2\). At \(k=1\), \(d_1=2>1\), so the implication passes. At \(k=2\), \(d_2=2\le2\), but the paired entry is \(d_{6-2}=d_4=2\), while the required threshold is \(6-2=4\). Since \(2<4\), the condition fails.

Check: The graph is nevertheless Hamiltonian: \(1,2,3,4,5,6,1\) is a cycle through all six vertices. The edge set has size \(7\); the degree sum is \(3+2+3+2+2+2=14=2\cdot7\). This example confirms that failing the condition does not establish non-Hamiltonicity.

Worked Example: A Non-Hamiltonian Graph That Fails

Let \(G\) have vertex set \(\{a,b,c,d,e\}\) and edge set \(\{ab,ac,ad,ae\}\). This is a star with center \(a\). Its sorted degree sequence is \(1,1,1,1,4\).

For \(n=5\), the allowed indices are \(k=1,2\). At \(k=1\), \(d_1=1\le1\), but \(d_{5-1}=d_4=1<4\). At \(k=2\), \(d_2=1\le2\), but \(d_{5-2}=d_3=1<3\). Both paired implications fail.

Check: The graph has four edges, and the degree sum is \(4+1+1+1+1=8=2\cdot4\). It cannot have a Hamiltonian cycle: each vertex on a cycle has two incident cycle edges, but each of \(b,c,d,e\) has degree \(1\). Here the failed test is consistent with non-Hamiltonicity; the previous example shows why failure alone is not a proof.

Relationship to a Minimum-Degree Bound

The condition also includes the familiar situation where the minimum degree is at least half the order. The following observation is about the inequalities themselves; it explains why such a degree bound makes every antecedent false.

Proposition: If \(n\ge3\) and \(\delta(G)\ge n/2\), then the degree sequence of \(G\) satisfies Chvatal’s condition.

Proof. Fix any allowed index \(k\), so \(k<n/2\). Every vertex degree is at least \(\delta(G)\), hence \(d_k\ge\delta(G)\ge n/2>k\). Therefore \(d_k\le k\) is false. The implication at this \(k\) is true, and this holds for every allowed \(k\). Thus all the paired inequalities pass. \(\square\)

By Chvatal’s theorem, a graph meeting this minimum-degree bound is Hamiltonian. The proposition does not say that the bound is necessary: the test can also pass when some degrees are below \(n/2\), as in the first worked example.

Common Pitfalls

Using the wrong paired entry. The entry paired with \(d_k\) is \(d_{n-k}\), not \(d_{n-k+1}\). In the first example, at \(k=2\) the correct entry is \(d_6=6\), and the threshold is \(8-2=6\). Comparing \(d_7\) instead would use the wrong index, even though its value also happens to be large enough.

Checking indices outside the range. The requirement is \(k<n/2\), not \(k\le n/2\). For \(n=8\), test \(k=1,2,3\); do not add \(k=4\). For \(n=6\), test \(k=1,2\), not \(k=3\).

Requiring the high-degree bound when the antecedent is false. A paired inequality is an implication. For instance, in the six-vertex example, \(k=1\) passes because \(d_1=2>1\); there is no requirement at that index that \(d_5\ge5\). Applying the conclusion regardless of the antecedent can incorrectly label a passing index as a failure.

Treating failure as a verdict. The theorem says that passing the test guarantees a Hamiltonian cycle. It does not say that every Hamiltonian graph passes. When an index fails, use another argument or method to decide Hamiltonicity; the criterion alone is inconclusive.

Check Your Understanding

For each question, pay attention to the strict index bound and to whether the antecedent of each implication holds.

For \(n=10\), list exactly the indices \(k\) that must be checked.
A graph of order \(7\) has sorted degree sequence \(2,2,3,4,4,5,6\). Check every paired inequality and state whether Chvatal’s theorem guarantees Hamiltonicity.
Explain why a failed paired inequality does not prove that a graph is non-Hamiltonian.
For \(n=6\), suppose \(d_2=2\) and \(d_4=4\). Does the implication at \(k=2\) pass? State both inequalities used.
Prove that if a graph has a Hamiltonian cycle, then every vertex has degree at least \(2\).