Number of Hamiltonian Cycles in Kn,n 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 Kn,n contain both the edges {$l_1, r_1$} and {$r_1, l_2$}?
And how about the number of Hamiltonian cycles in Kn,n that contain both the edges {$l_1, r_1$} and {$l_2, r_2$}?
Thanks!
 A: Pick any vertex, for simplicity let’s call it $l_1$. It doesn’t matter which vertex we pick since each Hamiltonian cycle is indifferent to the order of its vertices. $l_1$ has $n$ choices for a $r_i$ vertex to connect to next. This $r_i$ vertex has $n-1$ choices for a vertex $l_i$ to connect to next. Continuing in this fashion we see there are
$$n!(n-1)! \text{ Oriented Hamiltonian cycles}$$ We need to divide by two because we don’t care which direction we take to travel a Hamiltonian cycle.
$$\frac{1}{2}n!(n-1)!\text{ Hamiltonian cycles}$$
Then the number of these Hamiltonian cycles that also contain both those edges is given by 
$$\frac{1}{2}n!(n-1)!\frac{1}{{n\choose 2}}$$
$$(n-1)!(n-2)!$$
because $r_1$ has to choose $2$ out of $n$ vertices to connect to, but it must connect to $l_1$ and $l_2$ in order to include those edges.
For the second question first consider the graph $K_{n-2,n-2}$ with left and right vertices $\{l_3,...,l_n\}$ and $\{r_3,...,r_n\}$. This graph has $\frac{1}{2}(n-2)!(n-3)!$ Hamiltonian cycles. If we wanted to insert the edge $\{l_2,r_2\}$ into any of these cycles to get a new one, there are $2(n-2)$ edges to do so. If we wanted to in turn insert the edge $\{l_1,r_1\}$ into this cycle to get a new one, there would be $2(n-2)+1=2n-3$ edges to insert this new one in because we just added an edge. Thus, there are 
$$2(n-2)!(n-2)!(2n-3)$$ Hamiltonian cycles of $K_{n,n}$ that include those two edges.
