Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It seems to me like the answer should be $n!$. Since you can first select the first vertex, then select each remaining vertex until you've got them all in a permutation.

My textbook, however, says that the answer is $(1/2)(n-1)!$

Unfortunately, it doesn't explain why this is. Why is it?

share|improve this question

1 Answer 1

up vote 7 down vote accepted

The answer really depends on how we think that two Hamiltonian cycles are equal. Take $K_3$ as example. Let's call its vertices $1$, $2$ and $3$. Then do we consider $1\to2\to3\to1$ same as $2\to3\to1\to 2$? If yes, $1\to2\to3\to1$ is the same as $2\to3\to1\to 2$, which is the same as $3\to1\to2\to 3$ in $K_3$. Then we will have two Hamiltonian cycles $1\to 2\to3\to1$ and $1\to 3\to 2\to1$. Moreover, if we consider $1\to 2\to3\to1$ and $1\to 3\to 2\to1$ being the same because the second one is obtained by reversing direction the first one, then we have only one Hamiltonian cycle in $K_3$.

For general $K_n$, it's the same. $1\to2\to\cdots\to n\to1$ is the same as $2\to\cdots\to n\to1\to 2$ is the same as.... $n\to1\to 2\to\cdots \to n$. And the $1\to 2\to\cdots\to n\to1$ and $1\to n\to\cdots\to2\to1$ being the same because the second one is obtained by reversing direction the first one. So we have altogether $\frac{1}{2}(n-1)!$ Hamiltonian cycles in $K_n$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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