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)!$ ?
$\begingroup$
$\endgroup$
-
1$\begingroup$ Consider small examples like $K_{3,3}$ and count for yourself. $\endgroup$ – Moritz Nov 28 '15 at 10:53
-
3$\begingroup$ Whether you divide by $2$ or not depends on whether you consider a cycle to be the same if you reverse its direction. $\endgroup$ – hmakholm left over Monica Nov 28 '15 at 11:01
$\begingroup$
$\endgroup$
As the graph is the complete bipartite graph, we can count the number of cycle as :
- Choose an initial set
- On the first set, you have $n$ choices for the first vertex
- On the second again $n$ choices
- Then $n-1$ choices
- 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)!$$
Now, if you consider a cycle and its reverse as the same cycle, we you should divide this result by 2.
answered Feb 6 '19 at 12:58
