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!
On
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)$$
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.