How to Check Chvátal’s Condition
Chvátal’s degree-sequence condition turns a sufficient test for Hamiltonicity into a finite list of comparisons. The practical work is to sort the degrees, check the right indices, and apply the two inequalities with care: the first is strict, while the second is not. A failed comparison at even one index means the condition is not satisfied; it does not, by itself, show that the graph has no Hamiltonian cycle.
All graphs in this tutorial are finite and simple. A degree sequence is the list of vertex degrees in nondecreasing order, with repetitions included. A Hamiltonian cycle is a cycle that contains every vertex of the graph. A degree sequence is called graphical if it is the degree sequence of at least one simple graph.
The index range can be written as \(1\le k\le\lfloor(n-1)/2\rfloor\). Indeed, if \(n=2r\), the integers \(k<n/2=r\) are \(1,\ldots,r-1\), and \(\lfloor(n-1)/2\rfloor=r-1\). If \(n=2r+1\), they are \(1,\ldots,r\), and \(\lfloor(n-1)/2\rfloor=r\).
Proof. Write \(n=2r\) when \(n\) is even. The condition \(1\le k<n/2\) then becomes \(1\le k<r\), so the allowed integer values are \(1,\ldots,r-1\), which is the same as \(1,\ldots,\lfloor(n-1)/2\rfloor\). When \(n=2r+1\) is odd, the condition becomes \(1\le k<r+\tfrac12\), so the allowed integer values are \(1,\ldots,r\), again equal to \(1,\ldots,\lfloor(n-1)/2\rfloor\). These are all the eligible indices in both cases. \(\square\)
Chvátal’s theorem states that if a simple graph has \(n\ge3\) vertices and its degree sequence satisfies this condition, then the graph is Hamiltonian. This tutorial is about checking the condition, not reproving the theorem; its proof belongs to the earlier material on Chvátal’s theorem. The hypothesis \(n\ge3\) matters: for \(n=2\), there are no eligible indices, so the condition would hold vacuously even for \(K_2\), which has no Hamiltonian cycle.
A Reliable Index-by-Index Procedure
At each eligible index \(k\), first compare \(d_k\) with \(k\). If \(d_k>k\), that index passes without needing the other comparison. If this strict inequality fails, check whether \(d_{n-k}\ge n-k\). The index passes if that second inequality holds, including when there is equality. The entire sequence passes only if every eligible index passes.
Proof. At index \(k\), the condition is the logical alternative \(d_k>k\) or \(d_{n-k}\ge n-k\). The first alternative is false exactly when \(d_k\le k\), and the second is false exactly when \(d_{n-k}<n-k\). Thus the index fails exactly when both of those inequalities hold. Since the full condition requires every eligible index to pass, it fails exactly when at least one eligible index fails. This also shows why equality has different effects in the two comparisons: \(d_k=k\) does not satisfy \(d_k>k\), whereas \(d_{n-k}=n-k\) does satisfy \(d_{n-k}\ge n-k\). \(\square\)
A useful record for each check is the index \(k\), the two positions \(k\) and \(n-k\), and the outcome of each comparison. This makes it easier to catch off-by-one errors and to give a precise certificate of failure.
Worked Example: A Sequence That Satisfies the Condition
Consider the sequence \((2,3,4,4,4,5,6,6)\). To confirm it is graphical, take vertices \(a,b,c,d,e,f,g,h\) and edges \(ab,ac,ad,ae,af,ag,bc,bd,be,bf,bg,cd,ce,cf,dh,eh,fg\). Their degrees are \(6,6,5,4,4,4,3,2\), respectively, so the sorted degree sequence is the stated one. There are \(17\) listed edges, and the degree sum is \(2+3+4+4+4+5+6+6=34=2\cdot17\).
Here \(n=8\), so the eligible indices satisfy \(1\le k<4\), namely \(k=1,2,3\). Check them in order:
- At \(k=1\), \(d_1=2\), and \(2>1\). The index passes.
- At \(k=2\), \(d_2=3\), and \(3>2\). The index passes.
- At \(k=3\), \(d_3=4\), and \(4>3\). The index passes.
Every eligible index passes through the first alternative, so the degree sequence satisfies Chvátal’s condition. Since \(n=8\ge3\), Chvátal’s theorem guarantees that every simple graph with this degree sequence is Hamiltonian.
Check: The three comparisons just used are \(2>1\), \(3>2\), and \(4>3\). The degree sum is \(34\), and the displayed realization has \(17\) edges, independently confirming the sum is twice the edge count.
Worked Example: Finding a Failing Index
Consider \((2,2,3,3,4,5,6,7)\). A realization has vertices \(a,b,c,d,e,f,g,h\) and edges \(ab,ac,ad,ae,af,ag,ah,bc,bd,be,bf,bg,cd,ce,ch,df\). The degrees of \(a,b,c,d,e,f,g,h\) are \(7,6,5,4,3,3,2,2\), so the sorted sequence is the one given. The edge list has \(16\) edges, and the degree sum is \(2+2+3+3+4+5+6+7=32=2\cdot16\).
Again \(n=8\), so test \(k=1,2,3\). At \(k=1\), \(d_1=2>1\), so that index passes. At \(k=2\), the first alternative fails because \(d_2=2\) and \(2\not>2\). The other position is \(n-k=8-2=6\), and \(d_6=5\). Since \(5<6\), the second alternative also fails. Thus \(k=2\) is a certificate that the sequence does not satisfy Chvátal’s condition. In fact, at \(k=3\), \(d_3=3\not>3\) and \(d_5=4<5\), so that index fails as well.
This calculation says that Chvátal’s sufficient condition does not certify Hamiltonicity for graphs with this degree sequence. It does not say that every graph with this sequence is non-Hamiltonian: failure of a sufficient test is not a proof that its conclusion is false.
Check: At the first failing index, the relevant entries are \(d_2=2\) and \(d_6=5\). The comparisons are \(2\le2\) and \(5<6\), so neither required alternative holds.
Worked Example: Equality in the Second Alternative
Consider the sequence \((2,3,3,4,4,5,5)\). It is graphical: on vertices \(a,b,c,d,e,f,g\), use edges \(ab,ac,ad,ae,af,bc,bd,be,bf,cd,cg,de,fg\). The vertex degrees are \(5,5,4,4,3,3,2\), so the sorted sequence is the one given. There are \(13\) edges, and the degree sum is \(2+3+3+4+4+5+5=26=2\cdot13\).
Here \(n=7\), so \(1\le k<3.5\), giving \(k=1,2,3\). At \(k=1\), \(d_1=2>1\); at \(k=2\), \(d_2=3>2\). At \(k=3\), \(d_3=3\), so the strict comparison \(3>3\) is false. But \(n-k=7-3=4\), and \(d_4=4\ge4\). The second alternative holds exactly at equality, so \(k=3\) passes. The sequence satisfies the condition.
Check: The last index passes because \(d_{n-k}=d_4=4\) and \(n-k=4\), giving \(4\ge4\). Replacing that comparison by \(4>4\) would incorrectly reject this sequence.
Common Errors and Interpretation
Using the wrong position. At index \(k\), the second degree is \(d_{n-k}\), not \(d_{n-k+1}\). For example, with \(n=8\) and \(k=2\), the position is \(8-2=6\), so the entry to inspect is \(d_6\). In the failing example, that entry is \(5\), and the comparison is \(5\ge6\), which is false.
Changing which inequality is strict. The first alternative is \(d_k>k\); equality does not pass it. The second is \(d_{n-k}\ge n-k\); equality does pass it. The third example depends on that distinction.
Confusing a failed test with a negative conclusion. Chvátal’s theorem gives a sufficient condition: meeting the condition guarantees a Hamiltonian cycle when \(n\ge3\). If a sequence fails, this particular guarantee is unavailable. Hamiltonicity must be decided by other reasoning or another method; the failure alone settles nothing.
Ignoring the number of vertices. The test has no eligible indices when \(n=2\), since there is no integer \(k\) with \(1\le k<1\). The condition is then vacuously true as a list of comparisons, but the theorem’s hypothesis \(n\ge3\) is not met. Always state the order before applying the Hamiltonicity conclusion.
Write the graphical degree sequence as \(d_1\le\cdots\le d_n\), retaining repeated entries.
Check each integer \(k\) from \(1\) through \(\lfloor(n-1)/2\rfloor\).
At each \(k\), check \(d_k>k\); if it fails, check \(d_{n-k}\ge n-k\).
If every index passes, the condition holds. Otherwise give an index where both alternatives fail. For \(n\ge3\), a successful check permits Chvátal’s theorem to be applied.
This procedure matters because it separates computation from interpretation. A successful check is a certificate that the degree-sequence hypothesis of Chvátal’s theorem holds. A failed check is a certificate only that this hypothesis is absent. In either case, recording the index and the actual entries makes the conclusion verifiable.
Check Your Understanding
For each question, state the eligible indices before evaluating any comparisons.
- For \((1,2,3,3,4,5)\), list the eligible indices and determine whether the sequence satisfies Chvátal’s condition.
- For \(n=9\), what is the largest eligible index? Explain using the inequality \(k<n/2\).
- At an index \(k\), suppose \(d_k=k\) and \(d_{n-k}=n-k\). Does the index pass? Explain which alternative applies.
- For \(n=8\) and \(k=2\), which degree position is tested by the second alternative? Why is using \(d_7\) an indexing error?
- What does a failed index establish, and what does it not establish about Hamiltonicity?
- Why can the condition not be used with Chvátal’s theorem to conclude that \(K_2\) has a Hamiltonian cycle?