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.
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?
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.