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.


Solution

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

 Solution (source code)