# The number of Hamiltonian cycles in the complete bipartite graph

I know that in the complete bipartite graph $K_{n,n}$ , there is $\frac{n!(n-1)!}{2}$ or $n!(n-1)!$ Hamilton cycles. wiki says first, wolfram says the second one. I know that there is $2n$ ways to specify the "start", but why it goes like $n!(n-1)!$ ?

• Consider small examples like $K_{3,3}$ and count for yourself. – Moritz Nov 28 '15 at 10:53
• Whether you divide by $2$ or not depends on whether you consider a cycle to be the same if you reverse its direction. – hmakholm left over Monica Nov 28 '15 at 11:01

2. On the first set, you have $$n$$ choices for the first vertex
3. On the second again $$n$$ choices
4. Then $$n-1$$ choices
5. and so on $$\ldots$$
Therefore we count H=2(n!)(n!) Hamiltonian cycles. However, we count each cycles $$2n$$ times because for any cycle there are $$2n$$ possibles vertices acting as "start". therefore we have $$H = \frac{2(n!)^2}{2n}=n!(n-1)!$$