How can I find the number of Hamiltonian cycles in a complete undirected graph?

11
votes

Can someone explain how to find the number of Hamiltonian cycles in a complete undirected graph?

Wikipedia says that the formula is (n-1)!/2, but when I calculated using this formula, K3 has only one cycle and K4 has 5. Was my calculation incorrect?

3
algorithmgraphcycle
You have made an error when you have calculated the total number of cycles. A Hamiltonian cycle must include all the edges. k4 has only 3 such cycles and in total it has 5 cycles, so the formula is correct. - Anubhav
Anubhav is incorrect, a Hamiltonian cycle does not need to include all edges, it needs to include all nodes/vertices. - Milan Donhowe

3 Answers

27
votes

Since the graph is complete, any permutation starting with a fixed vertex gives an (almost) unique cycle (the last vertex in the permutation will have an edge back to the first, fixed vertex. Except for one thing: if you visit the vertices in the cycle in reverse order, then that's really the same cycle (because of this, the number is half of what permutations of (n-1) vertices would give you).

e.g. for vertices 1,2,3, fix "1" and you have:

123 132

but 123 reversed (321) is a rotation of (132), because 32 is 23 reversed.

There are (n-1)! permutations of the non-fixed vertices, and half of those are the reverse of another, so there are (n-1)!/2 distinct Hamiltonian cycles in the complete graph of n vertices.

3
votes

In answer to your Google Code Jam comment, see this SO question

-1
votes

I think when we have a Hamiltonian cycle since each vertex lies in the Hamiltonian cycle if we consider one vertex as starting and ending cycle . we should use 2 edges of this vertex.So we have (n-1)(n-2)/2 Hamiltonian cycle because we should select 2 edges of n-1 edges which linked to this vertex.