MathCastle
Graph TheoryChallengeEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Challenge problem

The pentagonal prism graph has two disjoint 55-cycles (call them the "top" 0,1,2,3,40,1,2,3,4 and the "bottom" 5,6,7,8,95,6,7,8,9) plus five rungs i (i+5)i\,(i+5) for i=0,…,4i=0,\dots,4, so every vertex has degree 33. Check that for EVERY pair of non-adjacent vertices in this 1010-vertex graph, Ore's theorem's degree-sum condition fails. Given that, how many distinct Hamiltonian cycles does the prism actually have?