Question 893328: HELP HOMEWORK!
If a complete graph has 12 vertices, how many distinct Hamilton circuits does it have?
Answer by richard1234(7193)   (Show Source):
You can put this solution on YOUR website! There are 12 ways to select the first vertex, 11 ways to select the second, etc. so intuitively the number of Hamiltonian cycles would be 12!. However this is not correct. We have to divide by 12 because 1 -> 2 -> ... -> 12 -> 1 is the same as 2 -> 3 -> ... -> 2, 3 -> 4 -> ... -> 3, etc. Also, because the graph is assumed to be undirected, the cycles 1 -> 2 -> ... -> 12 -> 1 and 1 -> 12 -> ... -> 2 -> 1 are counted, so we can divide by 2 for overcounting. The number of Hamiltonian cycles is 11!/2.
In general, the number of Hamiltonian cycles of a complete undirected graph with n vertices is (1/2)(n-1)!.
|
|
|
