Counting Hamilton circuits
Listing Hamilton circuits
A complete graph has an edge between every pair of
From now on we will consider only complete graphs.
So there are 4x3x2x1 = 24 Hamilton circuits (starting at a given
for a graph with 5 vertices.
In mathematics, 4x3x2x1 is denoted by 4! (4 factorial). Here's
our counting result:
(n-1)! Hamilton circuits
starting from a given vertex
How many Hamilton circuits (starting at a given vertex) are there
a complete graph of 10 vertices? Do it on your calculator (find
! key!): ··
How many for a complete graph of 50 vertices?··
For 3 vertices (A, B, C), there are 2! Hamilton circuits starting
A, and they are:
For 4 vertices, we need to add new vertex D.
Method: just insert D at all possible places, like so:
Voila! 3! = 6 of them!