# 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?

• What do you mean "right way to solve this problem"? The graph defined above is $K_{n, n}$, so finding the number of Hamiltonian cycles in $K_{n, n}$ solves the problem. Whether you consider the linked question a sufficient solution is up to you. – Mees de Vries Aug 31 '18 at 9:31

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:

1. 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).
2. 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.