3
$\begingroup$

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 6x2 = 12 directed cycles).

undirected Hamiltonian cycles for cubical graph

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Another way is to look at the faces. The cycle will split the 6 faces into two connected regions. Neither of those regions can contain three faces that meet at a corner, because then that corner is not visited by the cycle. Nor can a region be a single face or two adjacent faces (in either case the other region has 3 adjacent faces). So both regions consist of 3 faces in a row. This unique cycle shape can be oriented in 6 ways. $\endgroup$ – Jaap Scherphuis Aug 17 '17 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.