MathCastle
Graph TheorySuperchallengeEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Superchallenge problem

The Möbius ladder M5M_5 has 1010 vertices arranged on a 1010-cycle 0,1,…,90,1,\ldots,9 where ii connects to (i+1) mod 10(i+1) \bmod 10, plus five rungs ii to i+5i+5 for i=0,…,4i=0,\ldots,4 (every vertex has degree 33). Counting two Hamiltonian cycles as the same when they use the same set of edges, how many distinct Hamiltonian cycles does M5M_5 have?