0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Mees de Vries Aug 31 '18 at 9:31
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.