How many Hamiltonian circuits are there in a complete graph with n vertices?

Question

How many Hamiltonian circuits are there in a complete, undirected and simple graph with $n$ vertices?

The answer written in my book is: $$\frac{\left(n-1\right)!}{2}$$

What is the combinatorial explanation to this?

My best shot was to try to count for each size of Hamiltonian circuit (triangles, quadrilaterals, pentagons and so on), how many of each there is, and to sum them. So I tried to count for each amount of edges the amount as possibilities, to complete it to the mentioned shapes.

I mean for n vertices, I choose any 2 vertices (that's an edge) and for each other vertex by connecting from each vertex from my edge by new edges, I can create a triangle, which is a Hamiltonian circle of size 3 and so on. But there are a lot of repeats and that's a mess.

Maybe I didn't get the point at all, because the expression: $$\frac{\left(n-1\right)!}{2}$$

seems to be to me no more than the amount of Euler circles (each vertex degree is 2) which I order in a circle, so $(n-1)!$ is the possibilities to order $n$ different elements in a circle and divide by 2, because of the reflection.

Isn't a Hamiltonian circuit in such a graph an $n$-cycle, so it could be triangle, quadrilateral, and so on?

Answer 1

Any arrangement of the $n$ vertices yields a Hamiltonian cycle. In fact we may group the $n!$ possible arrangements in groups of $2n$ as one may choose any of the $n$ vertices to start from and any of the two directions to list the vertices in. It follows that there are precisely $\frac{n!}{2n}$ distinct Hamiltonian cycles. The result follows.

Further edit: Sketch of a more formal argument:

1. Let $A=\{(v_1,\dots,v_n):v_i\in V(G),v_i\ne v_j\mbox{ for } i\ne j\}$ be the set of all arrangements of the $n$ vertices. Show that $|A|=n!$.

2. Show that each $(v_1,\dots,v_n)$ yields a Hamiltonian cycle and all Hamiltonian cycles arise in this manner. (Many of these cycles are duplicates of each other.)

3. Consider an relation on $A$: $(v_1,\dots,v_n)\sim(w_1,\dots,w_n)$ if and only if $(v_1,\dots,v_n)$ and $(w_1,\dots,w_n)$ correspond to the same cycle. Prove that this is an equivalence relation.

4. Observe that each equivalence class will have precisely $2n$ elements. (Work out the case $n=5$ by hand)

5. Conclude that there are $n!/2n$ equivalence classes. Hence conclude there are $(n-1)!/2$ Hamiltonian cycles.