Hamiltonian paths in bipartite graphs

Question

Is there a way to find the exact number of Hamiltonian paths in special cases of bipartite graphs, for example, the K(n,n) complete bipartite graph for n ≥ 3?

Thanks.

Answer 1

For $K_{n,n}$, we denote its partitions as $A = \{a_1,...,a_n\}$ and $B = \{b_1,...,b_n\}$. Start from $a_1$, it has $n$ edges. wlog say next point is $b_1$, it will have $n-1$ edges to new vertices. wlog say next point is $a_2$, it will have $n-1$ edges to new vertices. wlog say next point is $b_2$, it will have $n-2$ edges to new vertices. And so on..

So total number of Hamiltonian paths = $n!(n-1)!$.

Using this you will be able to find #Hamiltonian paths for $K_{n,n-1}$ and maybe for regular ones. But in general one can't, since it is NP-Complete.