Why Count Components After Deleting Vertices?
A Hamiltonian cycle visits every vertex exactly once before returning to its start. Deleting a set of vertices from such a cycle breaks it into pieces, and the number of pieces cannot exceed the number of deleted vertices, provided the deleted set is nonempty. This gives a quantitative obstruction: if deleting a small set from a graph leaves many components, the graph cannot have a Hamiltonian cycle.
We make this idea precise with toughness. The parameter measures how many vertices must be deleted, relative to the number of components left behind. It supplies a necessary condition for Hamiltonicity, not a sufficient one.
The restriction \(c(G-S)>1\) ensures that the denominator is positive and that the deletion actually leaves more than one component. The minimum exists whenever the set of eligible \(S\)'s is nonempty, because a finite graph has only finitely many vertex sets. For a disconnected graph, \(S=\varnothing\) is eligible and gives ratio \(0/c(G)=0\), so its toughness is \(0\). For a complete graph, no deletion leaves more than one component, so the convention gives toughness \(\infty\).
A graph is Hamiltonian if it contains a cycle that includes every vertex. Such a cycle is called a Hamiltonian cycle. In a simple graph it has at least three vertices. We will compare the components left in \(G-S\) with the pieces left in a Hamiltonian cycle after the same vertices are deleted.
Deleting Vertices from a Cycle
Proof. Since \(S\) is proper, at least one vertex of \(C\) survives. List the vertices of the cycle in their cyclic order, marking each vertex as deleted or surviving. The surviving vertices split into maximal consecutive blocks: within a block, consecutive vertices are joined by cycle edges, while distinct blocks are separated by at least one deleted vertex. Each block is one component of \(C-S\). Going once around the cycle, every block is followed by at least one deleted vertex before the next block begins. Distinct blocks therefore correspond to distinct deleted vertices that immediately precede them in cyclic order. There are at most \(|S|\) such vertices, so the number of blocks, and hence \(c(C-S)\), is at most \(|S|\). \(\square\)
Both restrictions in the lemma matter. If \(S=\varnothing\), then \(c(C-S)=1\), which is not at most \(|S|=0\). If \(S=V(C)\), no vertices survive, and the block description does not apply; in fact \(c(C-S)=0\). The toughness argument will only need the nonempty, proper case.
The Hamiltonian Toughness Bound
Proof. Let \(G\) be Hamiltonian, and let \(S\subseteq V(G)\) be any set with \(c(G-S)>1\). Fix a Hamiltonian cycle \(C\) in \(G\). Since \(G\) is connected, \(c(G-\varnothing)=1\), so \(S\ne\varnothing\). Also, \(S\ne V(G)\), because deleting every vertex leaves zero components, not more than one. Thus \(S\) is a nonempty proper subset of the vertices of \(C\).
The subgraph \(C-S\) contains all the vertices of \(G-S\), and its edges are also edges of \(G-S\). Adding edges to a graph can merge components but cannot split one; consequently \(c(G-S)\le c(C-S)\). By the lemma, \(c(C-S)\le |S|\). Combining these inequalities gives \(c(G-S)\le |S|\). Since \(c(G-S)>1\), division by this positive number yields \(|S|/c(G-S)\ge1\). This holds for every eligible \(S\), so the minimum of these ratios is at least one. If there are no eligible sets, then \(\tau(G)=\infty\) by definition, and the bound also holds. \(\square\)
The comparison with \(C-S\) is the key step: the Hamiltonian cycle is a spanning subgraph, so it may have more components after deletion than the full graph does. The proof does not claim that the two component counts are equal.
Worked Example: Toughness of a Six-Cycle
Let \(G\) have \(V(G)=\{1,2,3,4,5,6\}\) and \(E(G)=\{12,23,34,45,56,61\}\). This is the cycle \(C_6\), so it is Hamiltonian. The theorem gives \(\tau(G)\ge1\).
To obtain an upper bound, delete \(S=\{1,4\}\). The surviving vertices are \(\{2,3,5,6\}\). Among them the surviving edges are \(23\) and \(56\), so \(G-S\) has exactly two components, \(\{2,3\}\) and \(\{5,6\}\). Substituting into the ratio gives \(|S|/c(G-S)=2/2=1\). Thus \(\tau(G)\le1\), and together with the theorem, \(\tau(G)=1\).
Check: the two surviving edges account for the components directly: each connects one pair, and there is no surviving edge between the pairs. The ratio is \(|\{1,4\}|/2=2/2=1\), matching the lower bound.
Worked Example: A Hamiltonian Graph with a Chord
Let \(G\) have \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,23,34,41,13\}\). The edges \(12,23,34,41\) form a Hamiltonian cycle, and \(13\) is a chord.
Delete \(S=\{1,3\}\). The remaining vertices are \(2\) and \(4\). The full edge list has no edge \(24\), so \(G-S\) consists of two isolated vertices and \(c(G-S)=2\). The resulting ratio is \(|S|/c(G-S)=2/2=1\). The theorem gives \(\tau(G)\ge1\), while this eligible set gives \(\tau(G)\le1\); therefore \(\tau(G)=1\).
Check: the chord \(13\) is deleted along with its endpoints, and none of the other listed edges has both endpoints in \(\{2,4\}\). Hence there are exactly two components, not one. Substitution gives \(2/2=1\) as claimed.
Worked Example: A Star Has Toughness Below One
Let \(G=K_{1,3}\), with \(V(G)=\{x,a,b,c\}\) and \(E(G)=\{xa,xb,xc\}\). Deleting the center \(x\) leaves three isolated vertices. Thus \(c(G-\{x\})=3\), and the ratio is \(|\{x\}|/3=1/3\). In particular, \(\tau(G)\le1/3\).
To verify that no eligible set gives a smaller ratio, first suppose the center \(x\) remains. If at least one leaf remains, every remaining leaf is connected to \(x\), so \(G-S\) is connected and \(S\) is not eligible. If no leaf remains, \(G-S\) has just the vertex \(x\), also not eligible. Therefore an eligible set must delete \(x\).
Write \(r\) for the number of leaves that remain after deleting \(x\). Eligibility requires \(r>1\), so \(r\) is either \(2\) or \(3\). The deletion set then has size \(4-r\), and \(G-S\) has \(r\) isolated components. For \(r=2\), the ratio is \((4-2)/2=2/2=1\); for \(r=3\), it is \((4-3)/3=1/3\). The minimum is \(1/3\), so \(\tau(G)=1/3\).
Check: the two possible eligible cases have ratios \(1\) and \(1/3\), and the smaller is the ratio obtained by deleting only the center. Thus this graph violates the Hamiltonian lower bound. Indeed, a cycle cannot pass through a degree-one vertex, so the star is not Hamiltonian.
Interpreting the Bound and Avoiding Pitfalls
The theorem says that a Hamiltonian graph cannot have a set \(S\) with \(c(G-S)>|S|\). Equivalently, every deletion that leaves more than one component must remove at least as many vertices as the number of components left. This is a necessary condition: a set violating it proves that a graph is not Hamiltonian. Passing the test does not, by itself, prove that a Hamiltonian cycle exists.
Common mistake: including the empty deletion in the cycle bound. A tempting but incorrect statement is \(c(C-S)\le |S|\) for every \(S\subseteq V(C)\). Taking \(S=\varnothing\) gives \(1\le0\), which is false because the intact cycle is connected. The correct lemma requires \(S\) to be nonempty and proper. In the Hamiltonian theorem, eligibility supplies both requirements: \(S=\varnothing\) leaves a connected graph, and \(S=V(G)\) leaves no components.
Another pitfall: reversing the component-count comparison. Since \(C-S\) is a subgraph of \(G-S\), the valid inequality is \(c(G-S)\le c(C-S)\): extra edges in \(G-S\) can join pieces that remain separate in the cycle. The reverse inequality need not hold. The proof uses the cycle to bound its own number of pieces, then uses that valid comparison to bound the number of components in \(G-S\).
Toughness is useful because it turns a structural question about a spanning cycle into a numerical test involving all vertex deletions. In applications, finding one violating set is enough to certify non-Hamiltonicity. Establishing that every eligible set has ratio at least one is more demanding, and even that lower bound only removes this particular obstruction.
Check Your Understanding
For each question, pay attention to whether the chosen deletion set leaves more than one component.
- Why must an eligible set \(S\) in a Hamiltonian graph be nonempty and proper?
- For a cycle \(C\), explain why the condition \(S\ne\varnothing\) is needed in the inequality \(c(C-S)\le |S|\).
- In the chorded four-vertex example, what would the ratio be if a deletion left only one component, and why would that deletion not enter the toughness minimum?
- For the star \(K_{1,3}\), compute the ratio when the center and exactly one leaf are deleted. Is this deletion eligible?
- Does \(\tau(G)\ge1\) prove that \(G\) is Hamiltonian? Explain what the theorem establishes and what it does not establish.