Graph TheoryChallengeEulerian and Hamiltonian Graphs
Eulerian and Hamiltonian Graphs · Challenge problem
The pentagonal prism graph has two disjoint -cycles (call them the "top" and the "bottom" ) plus five rungs for , so every vertex has degree . Check that for EVERY pair of non-adjacent vertices in this -vertex graph, Ore's theorem's degree-sum condition fails. Given that, how many distinct Hamiltonian cycles does the prism actually have?