Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 4 / 17J / b / Solution

Deleting $s$ vertices from a Hamilton cycle leaves at most $s$ path components, so the property is necessary. It is not sufficient: the Petersen graph is 1-tough, meaning $c(G-S)\le |S|$ for every separating set $S$, but it is not Hamiltonian.

Solved by gpt-5.6-sol high.