# Number of Hamiltonian cycles in $K{n,n}$ which contain specific edges

Suppose $$K_{n,n}$$ is a complete bipartite graph with vertices on left and right indexed by {$${l_1, l_2, ..., l_n}$$} and {$$r_1, r_2, ..., r_n$$} for $$n \geq 3$$.

I would like to ask how many Hamiltonian cycles in $$K_{n,n}$$ contain the edge {$$l_1, r_1$$}?

On the other hand, what about the Hamiltonian cycles in $$K_{n,n}$$ which DO NOT contain any edge from {$$l_1, r_1$$}, {$$r_1, l_2$$}, {$$l_2, r_2$$}?

Thanks!

## 2 Answers

To piggy back off of @Donald, I’ll answer the second question. Following @Donald’s reasoning there are in total $$\frac{n}{2}((n-1)!)^2$$ Hamiltonian cycles for $$K_{n,n}$$ provided $$n>1$$. We divide by two because $$n!(n-1)!$$ inadvertently assigns a clockwise/counter-clockwise direction to each Hamiltonian cycle. In order to consider such Hamiltonian cycles that don’t include $${l_1,r_1}$$ we must multiply this value by $$\frac{{n-1\choose 2}}{{n\choose 2}}$$ since $$l_1$$ has to choose $$2$$ vertices out of $$n$$ to connect to, but we are restricted to choosing out of a smaller pool of $$n-1$$ vertices.

Continuing in this fashion, we see that the number of Hamiltonian cycles that don’t include those three edges is $$\frac{n}{2}((n-1)!)^2\frac{{n-1\choose 2}}{{n\choose 2}}\frac{{n-2\choose 2}}{{n-1\choose 2}}\frac{{n-2\choose 2}}{{n-1\choose 2}}$$

$$\frac{1}{2}((n-2)!)^2(n-3)^2(n-2)$$

• you mentioned $n>1$ i am wondering is it also true for $n \geq 3$. However, is there a typo ? (replacement of the n of the term n / 2 to $n^{2}$ ? Thanks ! Commented Nov 29, 2019 at 6:23
• Yes the statement should be true for $n\geq 3$. I specified $n>1$ to guarantee the expression evaluates to an integer. In the case $n=1$ there are no Hamiltonian cycles. I’m not sure I understand what typo you’re referring to. $n$ is definitely meant to be divided by $2$.
– Ryan
Commented Nov 29, 2019 at 8:11
• I just find that $n((n-1)!)^{2} = n!(n-1)!$ , a careless mistake.... btw would you give some hints about the number of H with {$l_1, r_1$} and {$l_2, r_2$} ? Since they are not connect, i can't use @Donald's method Commented Nov 29, 2019 at 8:14
• You’re right. It was confusing for me to bring that up out of nowhere, but those two expressions are equivalent since $n\times (n-1)!$ is the same as just taking $n!$. Someone actually happened to post that question an hour after you made yours. My answer is here math.stackexchange.com/questions/3455014/…
– Ryan
Commented Nov 29, 2019 at 19:50

A Hamiltonian cycle will have the following form $$\begin{eqnarray*} l_1 r_1 l_{i_1} r_{j_1} \cdots l_{i_{n-1}} r_{j_{n-1}} \end{eqnarray*}$$ There are $$n-1$$ choices for $$i_1$$ an $$j_1$$. There are $$n-2$$ choices for $$i_2$$ and $$j_2$$, and so on until,there are $$1$$ choice for $$i_{n-1}$$ and $$j_{n-1}$$. So that makes $$((n-1)!)^2$$ Hamiltonian cycles.

• The second answer is incorrect. This can be seen from the $n=2$ case.
– Ryan
Commented Nov 28, 2019 at 22:20
• how about with the edge {$l_1, r_1$} and { $l_2, r_2$} ? thanks so much Commented Nov 29, 2019 at 7:36