A problem I'm working on reduced to finding a closed loop that visited every node of a cube. I remembered this was called a Hamiltonian cycle, and so I needed to find the number of Hamiltonian cycles.
I looked up there are 12 distinct directed Hamiltonian cycles for the cube (via MathWorld)
I worked out the 6 undirected cycles (as each path can go in 2 directions, this makes for a total of 6×2 = 12 directed cycles).
Is there a way to prove these are all of the distinct undirected Hamiltonian cycles? Or is it found by method of exhaustion (i.e., trial and error and basically finding that no other path works).
I'd be happy to cite Mathworld saying this is the answer, but it feels somewhat unsatisfying not to give further reason.
I did many, many web searches but kept finding complicated course notes unrelated to this question. I suspect it would be a basic graph theory question, but somehow a reference eludes me.
Please let me know if there's a way to prove there are 12 directed Hamiltonian cycles in a cubical graph. References would be much appreciated too–I am happy to work through some graph theory to understand why. Thanks!
Best Answer
Choose one point, arbitrarily (since the graph is symmetric). You can choose the Hamiltonian path through that vertex in $3$ ways, effectively choosing which of its incident edges will not be on the path. The adjacent vertex that will not now be adjacent on the path has also had its local path chosen, since we have removed the option of one edge.
To complete the path from these two short initial sections, one end is linked directly and the other end must be connected through the vertices not yet included on the path - $2$ choices. You can demonstrate this by choosing the non-connecting option at one end of a short section, then noticing that the other end of the same section must now directly connect to the other initial section of path to avoid a short cycle.
So there are a total of $3\times 2 = 6$ undirected Hamiltonian cycles for the cube, as you found.