Counting Hamiltonian cycles in a graph Given a graph $G = (W \cup U, E)$ where $W = \{w_1, w_2, ..., w_n\}$, $U = \{u_1, u_2, ..., u_n\}$ and $E = \{\{w_i, u_j\}: 1 \leq i, j \leq n\}$. The task is to calculate the number of Hamiltonian cycles in the graph G.
The way I tried solving was, 
Our vertex set $V = \{w_1, w_2 ... w_n, u_1, u_2, ... u_n\}$
Since we know 2 vertices $w_i \in W \text{ and } u_j \in U$ are adjacent if $1 \leq i, u \leq n$, this makes every vertex in W adjacent to every vertex in U giving us a bipartite graph. Also by Dirac's theorem
$deg(v) \leq \frac{|V|}{2}$ for a graph to be Hamiltonian.
So the task at hand condenses down to finding the number of hamiltonian cycles in a complete bipartite graph with n and n vertices i.e. $K_{n,n}$. Which is $\frac{n!(n-1)!}{2}$, taken from here.
Is this the right way to solve this problem or am i missing something?


Since we know 2 vertices $w_i \in W \text{ and } u_j \in U$ are adjacent if $1 \leq i, u \leq n$, this makes every vertex in W adjacent to every vertex in U giving us a bipartite graph.

The correct statement here would be:


*

*Since every edge is between a vertex in $W$ and a vertex in $U$, we have a bipartite graph. (The line I quoted from your proof doesn't say anything about edges in $W \times W$ or $U \times U$. Their non-existence is the crucial point).

*Since the edge set is the full Cartesian product $W \times U$, we have a complete bipartite graph.



So the task at hand condenses down to finding the number of
  hamiltonian cycles in a complete bipartite graph with n and n vertices
  i.e. $K_{n,n}$.

Correct.

Which is $\frac{n!(n-1)!}{2}$, taken from here.

Yes, but the main point of the exercise is probably to show why that's the correct result.
