MathCastle
Graph TheorySuperchallengeEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Superchallenge problem

The wheel graph W7W_7 has a hub joined to all 77 rim vertices of a 77-cycle 1,…,71,\ldots,7. What is the minimum number of vertices that must be deleted from this 88-vertex graph so that NO Hamiltonian cycle survives?