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)!$ ?

  • 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

As the graph is the complete bipartite graph, we can count the number of cycle as :

  1. Choose an initial set
  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)!$$

Now, if you consider a cycle and its reverse as the same cycle, we you should divide this result by 2.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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