Why is the number of Hamilton circuits in $K_{n,n}$ is $\frac{(n!)^2}{2n}$
Sebastian Wright 
Why is the number of Hamilton circuits in $K_{n,n}$ is $\frac{(n!)^2}{2n}$? I simply saw this in some previous exam of Graph-Theory.
I took for example $K_{2,2}$ and from each vertex I can go for two different paths to get a hamilton circuit, meaning there are $2 \cdot 4 = 8$ but according to the answer there is $1$.
$\endgroup$3 Answers
$\begingroup$Denote vertices $V := {l_1,\dots,l_n,r_1,\dots,r_n}$ ("left" and "right"). Since these are undirected cycles through all the vertices, we can freely choose a starting point. Make it $l_1$. You can choose your next vertex among all $n$ "right" vertices. Then $n-1$ "left" ones (all but $l_1$ which was used), then $n-1$ "right" ones (all but the one that came after $l_1$), and so on, until you use all the vertices.
Of course, connecting the first and the last vertex gives you a desired cycle.
So, the number of Hamilton paths/cycles generated this way is $$1 \cdot n \cdot (n-1) \cdot (n-1) \cdots 1 \cdot 1.$$ However, this will give you each path twice, because undirected paths $(x_1,x_2,\dots,x_{2n-1},x_{2n})$ and $(x_{2n},x_{2n-1},\dots,x_2,x_1)$ are the same (for $x_k \in V$).
So, finally, the number of possible Hamilton paths is $$\frac{1 \cdot n \cdot (n-1) \cdot (n-1) \cdots 1 \cdot 1}{2} = \frac{n \cdot n \cdot (n-1) \cdot (n-1) \cdot 1 \cdots 1}{2n} = \frac{(n!)^2}{2n}.$$
$\endgroup$ 2 $\begingroup$In $K_{2,2}$ there is one possible undirected Hamiltonian circuit, which looks like this:
For each vertex on the left you choose one edge to enter and the other to exit, but these choices are not independent: for each vertex on the right, one of the edges must enter and the other must exit.
EDIT: the $(n!)^2$ corresponds to a permutation of the "left" vertices and a permutation of the "right" vertices. Given those permutations (say $(a_1,\ldots,a_n)$ and $(b_1,\ldots,b_n)$, you can get a Hamiltonian path $(a_1, b_1, a_2, b_2, \ldots, a_n, b_n)$. Now divide by the number of different paths that correspond to the same undirected circuit.
$\endgroup$ 3 $\begingroup$Another way to see this is to start by considering Hamiltonian circuits with some extra information attached; think of a Hamiltonian circuit as a sequence of vertices, so it has a specific starting point and it has a specific direction in which to traverse the circuit. To make life a little easier, I'll consider only those sequences that start in the "left" half of your graph. So a Hamiltonian sequence is completely determined once you say (1) in which order the $n$ left vertices are visited and (2) in which order the $n$ right vertices are visited; furthermore, you can specify these two orders completely arbitrarily. Once the two orderings are specified, your sequence is obtained by just interleaving the left and right vertices, in the specified orders, and alternating between left and right, starting on the left. Since each side has $n$ points and therefore $n!$ possible orderings, the number of these "Hamiltonian sequences starting on the left" is $(n!)^2$. Now notice that each Hamilton circuit corresponds to exactly $2n$ of these "Hamiltonian sequences starting on the left", because, given a circuit, we have $n$ choices for the starting vertex (on the left) and $2$ choices for the direction to go around the circuit. So the number of Hamilton circuits is the number of Hamilton sequences starting on the left, divided by $2n$.
$\endgroup$
