Topics Complete graphs Counting Hamilton circuits Listing Hamilton circuits

A complete graph has an edge between every pair of vertices.

Example:

From now on we will consider only complete graphs.

So there are 4x3x2x1 = 24 Hamilton circuits (starting at a given vertex) 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 for a complete graph of 10 vertices? Do it on your calculator (find the ! key!): ··

How many for a complete graph of 50 vertices?··

For 3 vertices (A, B, C), there are 2! Hamilton circuits starting at A, and they are:

ABCA ACBA

For 4 vertices, we need to add new vertex D.

Method: just insert D at all possible places, like so:

ADBCA ABDCA ABCDA ADCBA ACDBA ACBDA

Voila! 3! = 6 of them!