0
$\begingroup$

The task is to find the count of hamiltonian cycle in $Q_3$. So I know the answer is $6$, but i don't know why or how to get it.

enter image description here

My first attempt was simple: I start from edge $6$, and I have $3$ $(2,5,8)$, then I have another $2$ (so I will get $3\cdot 2=6)$. But this doesn't help, because by choosing the first two edges of the cycle, we don't get any perticular Hamilton Cycle. Any tips?

$\endgroup$
0
$\begingroup$
  • You're right that you have six starting choices: 621, 624, 651, 657, 684, 687.

  • You can extend them further until they form a cycle. Some of the options will form the same cycle. For example, because order doesn't matter, 62157386 is the same Hamiltonian cycle as the reverse 68375126.

  • Using your procedure, starting from node 6, you have three choices, then two choices, then two choices, then one choice(!) for completing the rest of the Hamiltonian path. So altogether, it seems like there are 3*2*2 = 12 choices. However, we're counting each path twice. We need to consider the reverse of a path to be equivalent to the original path. When we do, there are actually six Hamiltonian paths altogether.

$\endgroup$

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.