1
$\begingroup$

There are a number of discussions online confirming that there exists a Hamiltonian cycle through the states of a Rubik's Cube. Or more precisely, the "quarter-turn metric Cayley graph for the Rubik's Cube" has a Hamiltonian cycle.

What about an Eulerian cycle, or even an Eulerian path?

$\endgroup$
4
$\begingroup$

Well, since an Eulerian cycle exists if and only if the degree of every vertex in a connected graph is even, we only need to check how many states it is possible to get to with one move (if a state is a vertex in our graph, then a move from one state to the next is an edge). In a Rubik's cube, we can get to a new state by rotating any one of the $9$ planes in $\mathit{either}$ direction, so we have $18$ possible states we can get to with one move. Noting that the graph is connected because we are only considering all possible states of the cube, we conclude that there is an Eulerian cycle.

$\endgroup$
  • $\begingroup$ There are actually only 6 planes you can rotate to get to a new state (in quarter turn metric anyway) but your result still holds. $\endgroup$ – timidpueo May 28 '14 at 15:42

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.