Why Vertex Deletion Can Obstruct a Hamiltonian Cycle
A Hamiltonian cycle visits every vertex exactly once before returning to its start. If some vertices are deleted, the remaining vertices occur in consecutive runs along that cycle. Each run is a path, and the deleted vertices separate one run from the next. This gives a restriction on how many components can remain: deleting a small set cannot split a Hamiltonian graph into too many pieces.
All graphs below are finite and simple. A component is a maximal connected subgraph; isolated vertices count as components. Write \(c(H)\) for the number of components of a graph \(H\), and set \(c(H)=0\) when \(H\) has no vertices. For \(S\subseteq V(G)\), \(G-S\) means the induced subgraph \(G[V(G)\setminus S]\): it keeps precisely the vertices outside \(S\) and all edges of \(G\) whose two endpoints remain. A Hamiltonian graph is a graph containing a cycle through every vertex exactly once.
The nonempty-set hypothesis matters. A Hamiltonian graph is connected, so \(c(G)=1\); for \(S=\varnothing\), the proposed bound would read \(1\le 0\), which is false. The theorem permits \(S=V(G)\), in which case \(G-S\) has no vertices and its component count is \(0\).
Proof from the Cyclic Order
Proof. Assume that \(G\) has a Hamiltonian cycle \(C\), and let \(S\ne\varnothing\). If \(S=V(G)\), then \(c(G-S)=0\le |S|\), so suppose that at least one vertex remains. Read the vertices in their cyclic order on \(C\), marking each vertex as either deleted (in \(S\)) or retained (outside \(S\)). The retained vertices split into \(r\) maximal consecutive runs in this cyclic order. Each run is connected by edges of \(C\), so it forms a path in \(G-S\), possibly a single vertex. Because at least one vertex is deleted, each run has a deleted vertex immediately before it in the cyclic order. Different runs have different immediately preceding deleted vertices: after any one deleted vertex, there is just one next run, before the next deleted vertex is reached. Thus these runs can be assigned distinct vertices of \(S\), and \(r\le |S|\). The cycle edges among retained vertices connect the vertices within each run; edges of \(G-S\) not on \(C\) may join different runs, but cannot split a run. Therefore \(G-S\) has at most \(r\) components. Hence \(c(G-S)\le r\le |S|\), as required. \(\square\)
The proof uses only the order of vertices on one Hamiltonian cycle. Extra edges in \(G\) can merge runs into larger components, which is why the conclusion is an upper bound rather than an equality. The theorem is a necessary condition: a violation rules out every possible Hamiltonian cycle, while a successful test for one set \(S\) does not establish that a Hamiltonian cycle exists.
Applying the Obstruction
Worked Example: A Hamiltonian Cycle with Three Deleted Vertices
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6,7\}\) and \(E=\{12,23,34,45,56,67,17\}\). This graph is the cycle \(1,2,3,4,5,6,7,1\), so it is Hamiltonian. Take \(S=\{1,3,5\}\), with \(|S|=3\). The remaining vertex set is \(V(G-S)=\{2,4,6,7\}\).
Among these remaining vertices, the only edge is \(67\): the edges \(12,23,34,45,56,17\) each have an endpoint in \(S\). Thus one component is the edge on \(\{6,7\}\), and the other two components are the isolated vertices \(2\) and \(4\). Therefore \(c(G-S)=3\), and the theorem’s bound is \(3\le |S|=3\).
Check: the remaining set has four vertices, but it does not have four components because \(6\) and \(7\) are adjacent. The count \(c(G-S)=3\) agrees with the three consecutive retained runs in the cycle: \(\{2\}\), \(\{4\}\), and \(\{6,7\}\).
Worked Example: A Deletion Set That Rules Out Hamiltonicity
Let \(G=(V,E)\), where \(V=\{x,a_1,b_1,a_2,b_2,a_3,b_3,a_4,b_4\}\) and \(E=\{xa_i,a_ib_i,b_ix:1\le i\le4\}\). Thus four triangles share the vertex \(x\), and there are no other edges. Take \(S=\{x\}\), so \(|S|=1\). After deleting \(x\), the remaining edges are \(a_1b_1,a_2b_2,a_3b_3,a_4b_4\). These four edges have pairwise disjoint vertex sets and there are no edges between them. Hence \(c(G-S)=4\).
Since \(4>1=|S|\), this graph violates the component-count condition and is not Hamiltonian. In fact, each \(a_i\) and \(b_i\) has degree \(2\), while \(x\) has degree \(8\): the obstruction is not that the vertices have degree less than \(2\), but that removing \(x\) leaves four separate pieces.
Check: the four components each contain two vertices, so they account for all eight vertices of \(G-S\). The inequality required of a Hamiltonian graph would be \(4\le1\), which is false.
Worked Example: A Deletion Test That Passes but Proves Little
Use the graph \(G=(V,E)\) with \(V=\{x,a_1,b_1,a_2,b_2,a_3,b_3,a_4,b_4\}\) and \(E=\{xa_i,a_ib_i,b_ix:1\le i\le4\}\). This graph is not Hamiltonian, as the deletion \(S=\{x\}\) in the previous example demonstrates. Now test a different set, \(T=\{a_1\}\), with \(|T|=1\).
After deleting \(a_1\), the remaining vertices are \(x,b_1,a_2,b_2,a_3,b_3,a_4,b_4\). The edge \(xb_1\) remains, and for each \(i\in\{2,3,4\}\), the edges \(xa_i\) and \(a_ib_i\) remain. Every remaining vertex is therefore connected to \(x\), so \(G-T\) is connected and \(c(G-T)=1\). This one test passes: \(1\le |T|=1\).
Check: passing the test for \(T\) does not contradict the graph’s non-Hamiltonicity. The theorem requires the inequality for every nonempty vertex set. For \(S=\{x\}\), the count is \(4>1\), so that set supplies the obstruction.
Worked Example: Deleting Vertices from a Complete Graph
Let \(G=K_5\), with \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,14,15,23,24,25,34,35,45\}\). The cycle \(1,2,3,4,5,1\) shows directly that \(G\) is Hamiltonian. Choose \(S=\{1,2\}\), so \(|S|=2\). The remaining vertices are \(\{3,4,5\}\), and all three edges \(34,35,45\) remain. Thus \(G-S\) is connected and \(c(G-S)=1\).
For this deletion, the bound reads \(1\le2\), and it is strict. The difference from the cycle example is that the remaining vertices are joined by several edges, so separate runs in a chosen cycle need not remain separate components in the full graph.
Check: the three remaining vertices form \(K_3\), which has one component; substituting the computed values gives \(c(G-S)=1\le |S|=2\).
How to Use the Condition
To apply the obstruction to a proposed Hamiltonian graph, choose a nonempty vertex set \(S\), delete it, and count the components of the induced graph that remains. If the count is greater than \(|S|\), the graph cannot be Hamiltonian. The vertices in \(S\) can be thought of as separators: along a Hamiltonian cycle, each deleted vertex can separate at most one new run of retained vertices. Finding more components than deleted vertices is therefore incompatible with a single cycle passing through all vertices.
The count is of components, not of remaining vertices, and isolated vertices must be included. Also, this is a vertex-deletion condition: \(G-S\) removes vertices and their incident edges. It is not an edge-deletion test. When applying it, record the remaining vertex set and the edges between those vertices before counting; this prevents both overlooking connections and missing isolated components.
Common Pitfall
Counting every remaining vertex as a separate component. In the 7-cycle example, deleting \(S=\{1,3,5\}\) leaves four vertices, but it does not leave four components: the edge \(67\) connects two of them. The correct calculation is \(c(G-S)=1+1+1=3\), from the component \(\{6,7\}\) and the isolated vertices \(\{2\}\) and \(\{4\}\). The bound is then \(3\le3\), not \(4\le3\).
Reversing the implication. A set with \(c(G-S)\le |S|\) has not certified Hamiltonicity; it has merely failed to produce an obstruction. For a non-Hamiltonicity certificate, one set with \(c(G-S)>|S|\) is enough. To pass this necessary condition, the inequality must hold for every nonempty \(S\), and even that conclusion is only that this particular obstruction has not ruled the graph out.
Check Your Understanding
For each question, count components in the vertex-deleted graph, including any isolated vertices.
- In the cycle \(C_8\) with vertices \(1,2,\ldots,8\) in cyclic order, delete \(S=\{1,3,5,7\}\). Find \(c(G-S)\) and compare it with \(|S|\).
- Suppose \(G\) is Hamiltonian and \(S=V(G)\). What is \(c(G-S)\), and why does the theorem still hold?
- A graph has a nonempty set \(S\) with \(c(G-S)=|S|+1\). What conclusion follows, and which implication of the theorem justifies it?
- In the four-triangle graph, why does testing \(T=\{a_1\}\) fail to establish Hamiltonicity even though \(c(G-T)\le |T|\)?
- Explain why the theorem counts components of \(G-S\), rather than simply counting vertices outside \(S\).