Using Connectivity and Independence Together
A graph can have many routes between its vertices and still contain a large set of pairwise nonadjacent vertices. The Chvátal–Erdős condition compares these two features: if vertex connectivity is at least the independence number, it guarantees a Hamiltonian cycle. Applying the condition requires more than calculating two numbers. One must justify both calculations and interpret the inequality in the correct direction.
All graphs in this tutorial are finite and simple. A Hamiltonian cycle is a cycle that visits every vertex exactly once before returning to its starting vertex. A set \(I\subseteq V(G)\) is independent if no two vertices in \(I\) are adjacent; the independence number \(\alpha(G)\) is the largest size of such a set.
In the examples below, to establish \(\kappa(G)=k\), we show both that deleting a particular set of \(k\) vertices disconnects the graph and that no set of fewer than \(k\) vertices does so. A set that disconnects the graph gives an upper bound on \(\kappa(G)\); ruling out all smaller cuts gives the matching lower bound.
A Reliable Application Procedure
For a specific graph, calculate and justify \(\kappa(G)\) and \(\alpha(G)\) separately before comparing them. Do not infer either number from a drawing alone: give a vertex-deletion argument for connectivity and an independent set together with an upper bound for its size.
Find a small vertex cut, then prove that deleting fewer vertices cannot disconnect the graph.
Exhibit an independent set and prove that no larger independent set can exist.
If \(\kappa(G)\geq\alpha(G)\), the theorem certifies a Hamiltonian cycle. If not, record that the condition does not certify one.
Worked Applications
Worked Example: The Complete Bipartite Graph \(K_{3,3}\)
Let \(G=K_{3,3}\) have vertex set \(A\cup B\), where \(A=\{a_1,a_2,a_3\}\), \(B=\{b_1,b_2,b_3\}\), and edge set \(E=\{a_i b_j:1\leq i\leq3,\ 1\leq j\leq3\}\). Thus every vertex in \(A\) is adjacent to every vertex in \(B\), and there are no edges within either part.
First compute \(\kappa(G)\). Deleting all three vertices of \(A\) leaves the three vertices of \(B\) with no edges, so the remaining graph is disconnected. Hence \(\kappa(G)\leq3\). Now delete any set of at most two vertices. At least one vertex of \(A\) and at least one vertex of \(B\) remain. Every remaining vertex in \(A\) is adjacent to every remaining vertex in \(B\). If two surviving vertices lie in different parts, they are adjacent; if they lie in the same part, they have a common neighbor in the other surviving part. Thus the remaining graph is connected, and \(\kappa(G)\geq3\). Therefore \(\kappa(G)=3\).
For \(\alpha(G)\), each part is independent, so an independent set of size \(3\) exists. An independent set cannot contain both a vertex of \(A\) and a vertex of \(B\), because every such pair is adjacent. Every independent set is therefore contained in one part and has size at most \(3\). Hence \(\alpha(G)=3\).
The comparison is \(\kappa(G)=3\geq3=\alpha(G)\), so the theorem certifies Hamiltonicity. For a direct check, the cycle \(a_1,b_1,a_2,b_2,a_3,b_3,a_1\) uses only edges between the two parts and visits all six vertices exactly once before returning.
Check: the listed cycle has six edges: \(a_1b_1,b_1a_2,a_2b_2,b_2a_3,a_3b_3,b_3a_1\). Each is in the specified edge set, and the six vertices before the return are distinct.
Worked Example: The Cycle \(C_6\)
Let \(G\) have \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,45,56,61\}\). To find \(\kappa(G)\), deleting any one vertex leaves a path through the other five vertices, which is connected. Thus no single vertex is a cut. Deleting vertices \(1\) and \(4\) leaves the edges \(23\) and \(56\), with no edge between these two pairs, so the remaining graph is disconnected. Therefore \(\kappa(G)=2\).
The set \(\{1,3,5\}\) is independent, since none of its three pairs is an edge, giving \(\alpha(G)\geq3\). The three edges \(12,34,56\) have disjoint endpoint sets and cover all six vertices. An independent set can contain at most one endpoint from each of these edges, so its size is at most \(3\). Thus \(\alpha(G)=3\).
Now \(\kappa(G)=2<3=\alpha(G)\). The Chvátal–Erdős condition does not certify Hamiltonicity here. It does not follow that \(G\) lacks a Hamiltonian cycle: the edge sequence \(1,2,3,4,5,6,1\) itself gives one, and each successive pair in the sequence is an edge in \(E\).
Check: the six vertices \(1,2,3,4,5,6\) are distinct before the return to \(1\), and the six required edges \(12,23,34,45,56,61\) are exactly the listed edges. Thus this graph is Hamiltonian even though the condition fails.
Worked Example: A Wheel with Four Rim Vertices
Let \(G\) have \(V=\{h,1,2,3,4\}\) and \(E=\{h1,h2,h3,h4,12,23,34,41\}\). The vertex \(h\) is adjacent to all four rim vertices, which form the cycle \(1,2,3,4,1\).
To compute \(\kappa(G)\), first consider deleting at most two vertices. If \(h\) remains, every other remaining vertex is adjacent to \(h\), so the remaining graph is connected. If \(h\) is deleted, at most one rim vertex has also been deleted; the remaining rim is either the full cycle or a path on three vertices, and is connected. Thus no set of at most two vertices disconnects \(G\). Deleting \(h,2,4\) leaves vertices \(1\) and \(3\), which are not adjacent, so the remaining graph is disconnected. Hence \(\kappa(G)=3\).
The hub \(h\) cannot belong to an independent set together with any other vertex. Among the four rim vertices, the adjacent pairs are \(12,23,34,41\), and the largest independent sets have size \(2\), for example \(\{1,3\}\). No independent set has size greater than \(2\): if it contains \(h\), it contains no rim vertex; if it does not contain \(h\), it lies on the rim, where choosing one rim vertex rules out its two neighbors and leaves at most one of the other two. Therefore \(\alpha(G)=2\).
Since \(\kappa(G)=3\geq2=\alpha(G)\), the condition certifies Hamiltonicity. Indeed, \(1,2,3,4,1\) is a cycle containing every rim vertex, and the full vertex set also has the Hamiltonian cycle \(h,1,2,3,4,h\).
Check: the five consecutive edges \(h1,12,23,34,4h\) are all listed in \(E\); the cycle visits \(h,1,2,3,4\) once each before returning to \(h\).
Interpreting the Result Correctly
The condition has a one-way logical form: \(\kappa(G)\geq\alpha(G)\) implies that \(G\) is Hamiltonian. A successful comparison is a certificate supplied by the theorem. A failed comparison only says that this particular sufficient condition is inconclusive. The \(C_6\) example makes the distinction concrete: its parameters fail the inequality, but its edges give a Hamiltonian cycle.
A common mistake is to reverse the implication. For example, after calculating \(\kappa(C_6)=2\) and \(\alpha(C_6)=3\), one might write “\(2<3\), so \(C_6\) is not Hamiltonian.” That conclusion is invalid: the theorem gives no conclusion from \(2<3\), and \(1,2,3,4,5,6,1\) is a Hamiltonian cycle. The correction is to report that the condition does not certify Hamiltonicity, then use another argument if a decision is required.
Another calculation pitfall is to establish only an upper bound on connectivity. Finding a cut of size \(3\) proves \(\kappa(G)\leq3\), not \(\kappa(G)=3\); the lower bound requires ruling out cuts of size \(0,1,\) and \(2\). Likewise, finding an independent set of size \(3\) proves only \(\alpha(G)\geq3\). To claim equality, an upper bound is also needed. The examples above supply both bounds before applying the theorem.
The condition is useful when connectivity and independent sets can be controlled more directly than Hamiltonian cycles themselves. Its conclusion is especially valuable because it turns two structural calculations into a guaranteed Hamiltonian cycle, without requiring that the cycle be found as part of the inequality test. In a problem, make the final statement match the evidence: say “Hamiltonian by the Chvátal–Erdős condition” when the inequality holds, and “the condition is inconclusive” when it does not.
Check Your Understanding
For each problem, justify the parameter calculations before applying or interpreting the condition.
- For \(K_{2,2}\), calculate \(\kappa(G)\) and \(\alpha(G)\). Does the Chvátal–Erdős condition certify Hamiltonicity?
- In the \(C_6\) example, why does finding a vertex cut of size \(2\) not by itself prove that \(\kappa(G)=2\)?
- Give an independent set of size \(2\) in the four-rim wheel and explain why no independent set can have size \(3\).
- A graph has \(\kappa(G)=3\) and \(\alpha(G)=4\). What, precisely, can you conclude from the Chvátal–Erdős condition?
- State the two bounds that must be proved to establish \(\alpha(G)=k\) for a proposed positive integer \(k\).