Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
up vote 8 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|cite|improve this answer

Easiest way to see this is to draw all possible Hamiltonians as figures - fairly easy to do for K4 say. You will then notice that of the 8 drawn, some are actually duplicated.. there are only 3.

I guess if you did this for K5 etc you would get a pattern to which 1/2(n-1)! is the answer

share|cite|improve this answer

Your Answer


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.