How many Hamiltonian cycles are there in a complete graph $K_n$ ($n\geq 3$) Why?

The answer really depends on how we think that two Hamiltonian cycles are equal. Take $K_3$ as example. Let's call its vertices $1$, $2$ and $3$. Then do we consider $1\to2\to3\to1$ same as $2\to3\to1\to 2$? If yes, $1\to2\to3\to1$ is the same as $2\to3\to1\to 2$, which is the same as $3\to1\to2\to 3$ in $K_3$. Then we will have two Hamiltonian cycles $1\to 2\to3\to1$ and $1\to 3\to 2\to1$. Moreover, if we consider $1\to 2\to3\to1$ and $1\to 3\to 2\to1$ being the same because the second one is obtained by reversing direction the first one, then we have only one Hamiltonian cycle in $K_3$.

For general $K_n$, it's the same. $1\to2\to\cdots\to n\to1$ is the same as $2\to\cdots\to n\to1\to 2$ is the same as.... $n\to1\to 2\to\cdots \to n$. And the $1\to 2\to\cdots\to n\to1$ and $1\to n\to\cdots\to2\to1$ being the same because the second one is obtained by reversing direction the first one. So we have altogether $\frac{1}{2}(n-1)!$ Hamiltonian cycles in $K_n$.


Just bringing in all related similar numbers of Hamiltonian circuits in complete graphs with possible intuitive interpretation of them:

Total (non-distinct) Hamiltonian circuits in complete graph $K_n$ is $(n-1)!$

This follows from the fact that starting from any vertex we have $n-1$ edges to choose from first vertex, $n-2$ edges to choose from second vertex, $n-3$ to choose from the third and so on. These being independent choices, we get $(n-1)!$ possible number of choices.

Number of distinct not edge disjoint Hamiltonian circuits in complete graph $K_n$ is $\frac{(n-1)!}{2}$

Above number ($(n-1)!$) is divided by $2$, because each Hamiltonian circuit has been counted twice (in reverse direction of each other like these: $A\rightarrow B \rightarrow C \rightarrow A$ and $A\rightarrow C \rightarrow B \rightarrow A$).

Number of edge disjoint Hamiltonian circuits in complete graph $K_n$ where $n$ is odd is $\frac{n-1}{2}$

We can realize this by arranging the vertices inside the circle as follows: enter image description here

There is only single edge connecting two vertices in upper half of circumference. Each such edge can lead to unique edge disjoint Hamiltonian circuit. We can rotate this circuit so that this edge gets mapped to the next pair of vertices on the upper half of the circumference which will lead to next unique edge disjoint Hamiltonian circuit. There are $\frac{n-1}{2}$ such consecutive pairs in the upper half of the circumference with $\frac{n-1}{2}$ edges connecting them each leading to unique edge disjoint Hamiltonian circuits.

Tags:

Graph Theory