Graph TheoryChallengeEulerian and Hamiltonian Graphs
Eulerian and Hamiltonian Graphs · Challenge problem
The pentagonal prism graph (two -cycles "top" and "bottom" , joined by rungs ) has a Hamiltonian cycle, as the top or bottom -cycle alone shows. What is the minimum number of vertices that must be deleted from the full -vertex graph so that NO Hamiltonian cycle survives among the remaining vertices and edges?