A Proof of the Chvatal–Erdos Theorem

The Condition and the Proof Strategy

The Chvátal–Erdős condition relates two different ways a graph can resist disruption. Vertex connectivity measures how many vertices must be removed to disconnect a graph; the independence number measures the size of a set of pairwise nonadjacent vertices. The theorem says that sufficiently high connectivity, compared with the largest independent set, guarantees a spanning cycle.

All graphs in this tutorial are finite and simple. A Hamiltonian cycle is a cycle containing every vertex of the graph. An independent set is a set of vertices no two of which are adjacent; the maximum size of such a set is \(\alpha(G)\). A vertex cut is a set \(S\subseteq V(G)\) whose deletion disconnects the graph. The vertex connectivity \(\kappa(G)\) is the minimum size of a vertex cut; we use the standard conventions \(\kappa(G)=0\) for a disconnected graph and \(\kappa(K_n)=n-1\). In particular, a graph with a single vertex has independence number \(1\) and connectivity \(0\).

The proof turns on a structural fact about non-Hamiltonian graphs: if a graph has no spanning cycle, a longest-path argument produces a vertex separator smaller than an independent set. The theorem then follows by comparing the sizes of these two sets. The separator fact is the substantive part of the argument, so it must not be replaced by an unsupported assertion.

The Longest-Path Separator Lemma

This tutorial invokes the lemma as an established result rather than presenting its technical proof. Its longest-path argument is a standard ingredient in proofs of the Chvátal–Erdős theorem; a source is V. Chvátal and P. Erdős, “A note on Hamiltonian circuits,” Discrete Mathematics 2 (1972), 111–113. Thus the theorem proof below is conditional on this specific separator lemma, not on an unstated claim: the lemma supplies exactly the independent set and separator needed for the contradiction.

To see how the lemma is used, suppose \(G\) is connected. Every vertex separator has size at least \(\kappa(G)\), by the definition of vertex connectivity. Every independent set has size at most \(\alpha(G)\), by the definition of the independence number. Consequently, for the sets furnished by the lemma,

This strict inequality is the obstruction: a non-Hamiltonian graph must have connectivity strictly smaller than its independence number. The assumption \(\kappa(G)\ge\alpha(G)\) rules out that possibility.

Proof of the Chvátal–Erdős Theorem

Proof. Let \(G\) have \(n\ge3\) vertices and suppose \(\kappa(G)\ge\alpha(G)\). Since \(V(G)\) is nonempty, it contains a one-vertex independent set, so \(\alpha(G)\ge1\). Hence \(\kappa(G)\ge1\), and \(G\) is connected under the stated convention for disconnected graphs. Assume for contradiction that \(G\) has no Hamiltonian cycle. The longest-path separator lemma gives a vertex separator \(S\) and an independent set \(I\) with \(|I|>|S|\). Since \(S\) is a separator in the connected graph \(G\), the definition of \(\kappa(G)\) gives \(\kappa(G)\le|S|\). Since \(I\) is independent, \(|I|\le\alpha(G)\). Combining these inequalities yields \[ \kappa(G)\le|S|<|I|\le\alpha(G), \] so \(\kappa(G)<\alpha(G)\). This contradicts the hypothesis \(\kappa(G)\ge\alpha(G)\). Therefore \(G\) has a Hamiltonian cycle. \(\square\)

The order assumption matters. For \(n=1\), the connectivity inequality fails under the conventions above. For \(n=2\), the usual definition of a cycle requires at least three vertices, so the conclusion would not hold even for \(K_2\). The theorem is stated for \(n\ge3\) to avoid both degenerate cases.

Worked Examples: Checking the Parameters

What the Proof Does—and Does Not—Say

The theorem is a sufficient condition, not a characterization. It guarantees Hamiltonicity when \(\kappa(G)\ge\alpha(G)\); if the inequality fails, that fact alone says nothing about whether a Hamiltonian cycle exists. A failure of the hypothesis is not a proof that the graph is non-Hamiltonian, as the implication in the theorem runs only from the parameter inequality to the existence of a cycle.

There is also a useful converse-style obstruction that follows from the same separator lemma: if a graph of order at least \(3\) is non-Hamiltonian, then \(\kappa(G)<\alpha(G)\). Indeed, the lemma gives \(\kappa(G)\le|S|<|I|\le\alpha(G)\), provided the graph is connected; if it is disconnected, \(\kappa(G)=0<\alpha(G)\) directly. This is a necessary inequality for non-Hamiltonicity, not a claim that every graph with \(\kappa(G)<\alpha(G)\) is non-Hamiltonian.

A further consistency check is that every Hamiltonian graph of order at least \(3\) has connectivity at least \(2\). To verify this, deleting any one vertex from a Hamiltonian cycle leaves a path through all remaining vertices, so the remaining graph is connected. Thus no single vertex is a cut, and \(\kappa(G)\ge2\). The Chvátal–Erdős condition is stronger in a different direction: it compares connectivity with the size of a largest independent set.

Common Pitfalls

Reversing the inequality. The theorem requires \(\kappa(G)\ge\alpha(G)\), not \(\kappa(G)\le\alpha(G)\). For the star above, the incorrect check \(1\le3\) might be misread as satisfying the theorem. The correction is to substitute into the stated condition: \(1\ge3\) is false, so the theorem gives no conclusion.

Skipping the separator step. It is not enough to say that a longest path somehow creates an independent set larger than connectivity. The separator lemma has a precise conclusion, \(|I|>|S|\); the proof then needs both \(\kappa(G)\le|S|\) and \(|I|\le\alpha(G)\) to produce the contradiction. Leaving out either comparison does not establish the theorem.

Confusing an independent set with a separator. These are different objects: independence concerns adjacency among selected vertices, while a separator disconnects the graph when removed. The theorem’s proof compares their cardinalities but does not claim that one set is the other.