11

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?

Jason Plank
  • 2,336
  • 5
  • 31
  • 40
avd
  • 13,993
  • 32
  • 78
  • 99
  • 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 Apr 19 '13 at 17:30
  • Anubhav is incorrect, a Hamiltonian cycle does not need to include all edges, it needs to include all nodes/vertices. – Milan Donhowe May 18 '20 at 19:52

3 Answers3

28

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.

Jonathan Graehl
  • 9,182
  • 36
  • 40
  • I asked this questions in relation to a last year Code Jam Question. But I am still not able to figure out the algorithm Can u please explain this Code Jam question http://code.google.com/codejam/contest/dashboard?c=32004#s=p2 – avd Sep 07 '09 at 04:45
  • 1
    I'd generate all the permutations of 2...n where 2 comes in the first half, and skip over those that give one of the forbidden edges, i.e. if your permutations is 4235 (meaning the cycle 142351...) then skip it if 14 42 23 35 or 51 are forbidden. You can do this as you generate the permutations e.g. if 14 was forbidden, then you would have stopped at "4..." – Jonathan Graehl Sep 07 '09 at 05:16
  • But if number of vertices is very large say 30 then generating all permutations i.e. 29!/2 is computationally very expensive – avd Sep 07 '09 at 05:21
  • One more thing why did u say "where 2 comes in the first half"? What does this mean? – avd Sep 07 '09 at 05:27
  • Well, I just wanted some way of distinguishing the permutation p from reverse(p). One way to do that is to pick an element (I picked 2) and ensure that it occurs in the first half. – Jonathan Graehl Sep 07 '09 at 05:39
  • You're right that my suggestion for a 30 or 300 node graph is impractical. It seems like a tricky problem. Did you know you can download people's source code who've solved it? – Jonathan Graehl Sep 07 '09 at 05:40
  • All the vertices not adjacent to one of the prohibited 0-15 edges are indistinguishable, so there's no need to actually generate the permutations of those indistinguishable vertices. Just using that fact should make it tractable. – Jonathan Graehl Sep 07 '09 at 05:56
3

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

Community
  • 1
  • 1
xan
  • 7,511
  • 2
  • 32
  • 45
-1

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.

user3591890
  • 11