A Proof of Chvatal's Theorem

The Degree-Sequence Condition

A Hamiltonian cycle visits every vertex exactly once before returning to its starting vertex. Chvátal’s theorem gives a sufficient condition for such a cycle using only the sorted list of degrees. The proof uses an extremal idea: among graphs on the same vertex set that are not Hamiltonian, choose one to which no edge can be added while keeping it non-Hamiltonian. The crucial step is to show that this maximal graph’s degree sequence fails the condition. That step requires a separate extremal lemma, so we will identify its role explicitly rather than hide it inside the argument.

All graphs below are finite and simple. A graph is Hamiltonian if it contains a cycle passing through every vertex exactly once. For a graph of order $n$, write its degrees in nondecreasing order as $d_1\le d_2\le\cdots\le d_n$. The indices in the condition below are integers.

Definition: A degree sequence $d_1\le\cdots\le d_n$ satisfies Chvátal’s condition if, for every integer $k$ with $1\le k<n/2$, either $d_k>k$ or $d_{n-k}\ge n-k$. Equivalently, whenever $d_k\le k$, the degree at the opposite index must satisfy $d_{n-k}\ge n-k$.

The index range is important: for $n=4$, only $k=1$ is tested; for $n=5$, $k=1,2$ are tested. The condition is sufficient, not a characterization: failure of the condition does not by itself prove that a graph is non-Hamiltonian.

Maximal Non-Hamiltonian Graphs

Definition: A graph $G$ is edge-maximal non-Hamiltonian if $G$ is not Hamiltonian, but $G+e$ is Hamiltonian for every edge $e$ joining two nonadjacent vertices of $G$. “Maximal” here refers to adding edges on the same vertex set; it does not mean that $G$ has as many edges as possible among all non-Hamiltonian graphs of every order.

If a non-Hamiltonian graph is given on a fixed vertex set, an edge-maximal non-Hamiltonian graph containing it can always be chosen. There are only finitely many possible edges on that vertex set. Repeatedly add a missing edge whenever the graph remains non-Hamiltonian. This process must stop, and when it stops the graph has the stated maximality property.

We also need a simple monotonicity fact. It explains why the degree-sequence condition survives the edge additions in this process.

Lemma: If $H$ is obtained from $G$ by adding edges on the same vertex set, then the $i$-th smallest degree of $H$ is at least the $i$-th smallest degree of $G$, for every $i$. Consequently, if the degree sequence of $G$ satisfies Chvátal’s condition, then so does the degree sequence of $H$.

Proof. Each vertex degree can only stay the same or increase when edges are added. Suppose the $i$-th smallest degree in $G$ is $a$. At least $n-i+1$ vertices have degree at least $a$ in $G$; these same vertices have degree at least $a$ in $H$. Therefore at most $i-1$ vertices of $H$ have degree less than $a$, so the $i$-th smallest degree in $H$ is at least $a$. Now suppose the sequence of $G$ satisfies the condition and $d_k(H)\le k$. Since $d_k(G)\le d_k(H)$, we have $d_k(G)\le k$, so $d_{n-k}(G)\ge n-k$. Monotonicity gives $d_{n-k}(H)\ge d_{n-k}(G)\ge n-k$. This proves the condition for $H$. $\square$

The Essential Extremal Lemma

The following statement is the key bridge from maximal non-Hamiltonicity to a degree-sequence contradiction. Its conclusion supplies one particular index $k$, not merely a general restriction on the degrees of nonadjacent vertices.

Lemma (maximal non-Hamiltonian degree-sequence lemma): If $G$ is an edge-maximal non-Hamiltonian graph of order $n\ge3$, then there is an integer $k$ with $1\le k<n/2$ such that its sorted degree sequence satisfies $$ d_k\le k \qquad\text{and}\qquad d_{n-k}\le n-k-1. $$ In particular, the degree sequence of $G$ fails Chvátal’s condition.

This lemma is a substantive part of the proof, not a consequence of the definition of maximality alone. For example, maximality says that adding any missing edge creates a Hamiltonian cycle; it does not, without further argument, identify an index $k$ with both displayed degree bounds. The full proof of this extremal lemma is not given here. It is stated as a standard result; see V. Chvátal, “On Hamilton’s ideals,” Journal of Combinatorial Theory, Series B 12 (1972), 163–168.

It is useful to separate this lemma from the deduction that uses it. The deduction below is conditional on the lemma: it shows exactly how the lemma proves Chvátal’s theorem, and does not claim to derive the lemma from the preceding material.

The Conditional Deduction of Chvátal’s Theorem

Theorem (Chvátal): Let $G$ be a finite simple graph of order $n\ge3$, with sorted degree sequence $d_1\le\cdots\le d_n$. If the sequence satisfies Chvátal’s condition, then $G$ is Hamiltonian.

Proof, conditional on the maximal non-Hamiltonian degree-sequence lemma. Suppose, for contradiction, that $G$ satisfies Chvátal’s condition but is not Hamiltonian. Among the non-Hamiltonian graphs on $V(G)$ that contain all the edges of $G$, choose one, $H$, with as many edges as possible. Such a choice exists because the vertex set is fixed and finite, and $G$ is one of the graphs being considered. The graph $H$ is edge-maximal non-Hamiltonian: if a missing edge could be added while keeping the graph non-Hamiltonian, the result would be a graph in the same collection with more edges.

By the monotonicity lemma, the degree sequence of $H$ still satisfies Chvátal’s condition, since $H$ was obtained from $G$ by adding edges. But the maximal non-Hamiltonian degree-sequence lemma gives an index $k$ with $1\le k<n/2$, $d_k(H)\le k$, and $d_{n-k}(H)\le n-k-1$. Chvátal’s condition applied to that same $k$ requires $d_{n-k}(H)\ge n-k$. The two inequalities are incompatible, since $n-k-1<n-k$. This contradiction proves the theorem, provided the stated extremal lemma is available. $\square$

The proof’s logical structure matters. Choosing an edge-maximal counterexample is valid because there are finitely many edge sets on a fixed vertex set. The monotonicity lemma preserves the condition during edge additions. The contradiction then depends on the extremal lemma producing the required index. Without a proof or an explicit citation for that lemma, the deduction alone would not establish the theorem.

Worked Examples

Worked Example: An Edge-Maximal Non-Hamiltonian Graph

Let $G$ have vertex set $V=\{a,b,c,d\}$ and edge set $E=\{ab,bc,ca,ad\}$. Its degrees are $\deg(a)=3$, $\deg(b)=2$, $\deg(c)=2$, and $\deg(d)=1$. Thus the sorted degree sequence is $1,2,2,3$.

The graph is not Hamiltonian because $d$ has degree $1$, whereas every vertex on a cycle must have at least two incident edges in the graph. Its missing edges are $bd$ and $cd$. Adding $bd$ gives the cycle $d,a,c,b,d$, using edges $da,ac,cb,bd$. Adding $cd$ gives the cycle $d,a,b,c,d$, using edges $da,ab,bc,cd$. These are all the missing edges, so $G$ is edge-maximal non-Hamiltonian.

Here $n=4$, so the only tested index is $k=1$. The sequence has $d_1=1\le1$ and $d_3=2\le2=4-1-1$. Thus it exhibits the failure asserted by the maximal non-Hamiltonian degree-sequence lemma. Check: Chvátal’s condition would require $d_3\ge3$ when $d_1\le1$, but the computed value is $d_3=2$, so the condition fails.

Worked Example: The Condition Survives Adding an Edge

Let $G$ have $V=\{1,2,3,4\}$ and $E=\{13,14,23,24,34\}$, so the only missing edge is $12$. Vertices $1,2$ have degree $2$, and vertices $3,4$ have degree $3$. Its sorted sequence is $2,2,3,3$.

For $n=4$, test only $k=1$. Since $d_1=2>1$, the condition holds. Add the missing edge $12$. The resulting graph is $K_4$, and each vertex has degree $3$, so the new sequence is $3,3,3,3$. Again $d_1=3>1$, so the condition holds.

Check: the only degree changes are those of vertices $1$ and $2$, each increasing from $2$ to $3$; the sorted entries have changed from $2,2,3,3$ to $3,3,3,3$, none decreasing. This agrees with the monotonicity lemma.

Worked Example: A Sequence That Fails the Condition

Let $P$ have $V=\{1,2,3,4,5\}$ and $E=\{12,23,34,45\}$. The endpoint degrees are $\deg(1)=\deg(5)=1$, and the other degrees are $\deg(2)=\deg(3)=\deg(4)=2$. The sorted sequence is $1,1,2,2,2$.

For $n=5$, the tested indices are $k=1,2$. At $k=1$, $d_1=1\le1$, but $d_4=2<4=5-1$, so the condition fails. At $k=2$, $d_2=1\le2$, but $d_3=2<3=5-2$, so it fails there as well.

Check: this graph is not Hamiltonian because vertices $1$ and $5$ each have degree $1$. Any cycle through either endpoint would need two distinct incident edges at that endpoint, but only one is available. The failure of the condition is consistent with non-Hamiltonicity; by itself, such a failure would not prove non-Hamiltonicity for every graph.

What the Maximal-Graph Argument Does—and Does Not Do

The extremal method is useful because it reduces a question about an arbitrary counterexample to one with a strong edge-addition property. However, the reduction has two logically separate parts:

Passing to a maximal non-Hamiltonian supergraph preserves Chvátal’s condition, by the proved monotonicity lemma.
Showing that this maximal graph violates the condition requires the maximal non-Hamiltonian degree-sequence lemma.

The first part is short and follows directly from how sorted degrees change. The second is the technical heart of this proof strategy. In particular, merely showing that every added nonedge would create a Hamiltonian cycle does not itself show that some index $k$ has $d_k\le k$ and $d_{n-k}\le n-k-1$. That index must be established by the extremal lemma.

Thus the theorem’s deduction is transparent once the lemma is supplied, but a complete proof from first principles also needs a proof of that lemma. Keeping this dependency visible prevents a conditional argument from being mistaken for a self-contained derivation.

Check Your Understanding

Use the definitions and the distinction between the lemma and its consequence to answer the following.

For $n=7$, list all indices $k$ that must be checked in Chvátal’s condition.
Explain why adding edges cannot decrease the $i$-th smallest degree, even though the ordering of the vertices by degree may change.
For the graph with $V=\{a,b,c,d\}$ and $E=\{ab,bc,ca,ad\}$, compute the sorted degree sequence and identify the index witnessing failure of the condition.
Why does selecting an edge-maximal non-Hamiltonian supergraph require fixing the vertex set?
Which part of the deduction of Chvátal’s theorem is not proved by the monotonicity lemma alone?

What You'll Learn