The Chvatal–Erdos Hamiltonicity Condition

Connectivity and Independence as a Hamiltonicity Condition

A Hamiltonian cycle must visit every vertex while returning to its starting point. A graph with a large independent set has many vertices that cannot be consecutive on such a cycle, while a graph with high vertex connectivity is resistant to disconnection when vertices are removed. The Chvatal–Erdos condition compares these two features: for graphs of order at least three, connectivity at least as large as the independence number guarantees a Hamiltonian cycle.

All graphs in this tutorial are finite and simple. An independent set is a set of vertices no two of which are adjacent. The independence number \(\alpha(G)\) is the largest size of an independent set in \(G\). A vertex cut is a set of vertices whose deletion disconnects a connected graph. For a connected noncomplete graph, the vertex connectivity \(\kappa(G)\) is the minimum size of a vertex cut. We use the standard conventions \(\kappa(K_n)=n-1\) and \(\kappa(G)=0\) when \(G\) is disconnected. These conventions make \(\kappa\) defined for the graphs considered below.

The Chvatal–Erdos condition is a sufficient condition, not a definition of Hamiltonicity. Its comparison is between two different parameters: \(\kappa(G)\) measures how many vertices must be removed to cause disconnection, while \(\alpha(G)\) measures the largest set of mutually nonadjacent vertices. The condition can apply even when \(\kappa(G)\) is strictly larger than \(\alpha(G)\), as well as when they are equal.

The Theorem and Its Deletion Threshold

The inequality has a precise deletion interpretation. If \(\kappa(G)\ge\alpha(G)\), then deleting any set of fewer than \(\alpha(G)\) vertices cannot disconnect \(G\). This does not assert that deleting every set of at least \(\alpha(G)\) vertices disconnects the graph, or that the graph remains connected after those deletions. The threshold concerns sets with size strictly less than \(\alpha(G)\).

For example, if \(\kappa(G)=\alpha(G)=2\), every deletion of zero or one vertex leaves the graph connected. The condition does not require the graph to remain connected after deleting two vertices. A two-vertex deletion may disconnect it without contradicting the theorem.

Two Basic Facts About the Parameters

The following elementary results help interpret the theorem. They do not prove the Chvatal–Erdos theorem; its proof is treated separately.

Proof. First suppose \(G\) is connected and noncomplete. Choose a vertex \(v\) of minimum degree, so \(\deg(v)=\delta(G)\). Since \(G\) is noncomplete, \(v\) is not adjacent to every other vertex. Thus some vertex \(w\ne v\) is not in \(N(v)\). Delete \(N(v)\). Both \(v\) and \(w\) remain, and \(v\) is isolated in the remaining graph. Therefore the remaining graph is disconnected, so \(N(v)\) is a vertex cut and \(\kappa(G)\le |N(v)|=\deg(v)=\delta(G)\). If \(G=K_n\), then \(\kappa(G)=n-1=\delta(G)\). If \(G\) is disconnected, then \(\kappa(G)=0\le\delta(G)\), since degrees are nonnegative. \(\square\)

Proof. A Hamiltonian cycle shows that the graph is connected, so its connectivity is not \(0\). Now delete any one vertex from a Hamiltonian cycle. The remaining cycle edges form a path through all the other vertices. That path connects all vertices that remain, so deletion of one vertex does not disconnect the graph. Thus no set of zero or one vertices disconnects it, and \(\kappa(G)\ge2\). \(\square\)

The second proposition is a necessary condition for Hamiltonicity, whereas the Chvatal–Erdos theorem gives a sufficient condition. They should not be conflated: the theorem’s hypothesis is the stronger comparison \(\kappa(G)\ge\alpha(G)\), not merely \(\kappa(G)\ge2\).

Worked Examples

Common Pitfall: Misreading the Deletion Count

For the five-cycle in the first example, a tempting but incorrect calculation is: “Deleting \(\{1,3\}\) disconnects the graph, so \(\kappa(G)=1\).” This counts the wrong number of deleted vertices: the displayed set has size \(2\), not \(1\). To compute connectivity, one must find the smallest size of a set whose deletion disconnects the graph. Deleting no vertices or one vertex leaves the five-cycle connected, while the two-vertex set \(\{1,3\}\) disconnects it. Hence \(\kappa(G)=2\), as calculated.

The same example corrects a related misreading of the theorem. The theorem does not say that connectivity at least \(\alpha(G)\) guarantees connectedness after deleting at least \(\alpha(G)\) vertices. For this graph, \(\kappa(G)=\alpha(G)=2\), and deleting \(\{1,3\}\), a set of size \(2\), does disconnect it. The actual implication is that deleting any set of fewer than \(2\) vertices leaves it connected.

A second logical error is to treat failure of the inequality as evidence of non-Hamiltonicity. The theorem has the form “if the condition holds, then the graph is Hamiltonian.” It does not assert that every Hamiltonian graph satisfies the condition. When the inequality fails, this criterion simply does not decide the question; another argument is needed.

Using the Condition

To apply the theorem, first verify that the graph has at least three vertices. Then determine the largest independent set and the minimum number of vertices whose deletion disconnects the graph (using the stated conventions for complete or disconnected graphs). Compare the resulting integers in the direction \(\kappa(G)\ge\alpha(G)\). Equality is enough, as the five-cycle demonstrates.

Computing these parameters can itself require substantial work on a large graph. The theorem is a certification tool once the comparison is known: if the inequality holds, a Hamiltonian cycle exists. It does not say that every graph with a Hamiltonian cycle will pass this test, nor does it provide a procedure for locating the cycle. Keep the mathematical conclusion separate from the task of finding an explicit cycle.