MathCastle
Graph TheoryChallengeEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Challenge problem

The pentagonal prism graph (two 55-cycles "top" 0,…,40,\ldots,4 and "bottom" 5,…,95,\ldots,9, joined by rungs i (i+5)i\,(i+5)) has a Hamiltonian cycle, as the top or bottom 55-cycle alone shows. What is the minimum number of vertices that must be deleted from the full 1010-vertex graph so that NO Hamiltonian cycle survives among the remaining vertices and edges?