6.2 Complete Graphs

Complete graphs

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

Example:

• Sophie's "map" has a direct route between every two cities
• therefore, the graph model of her problem has an edge between every pair of vertices:

From now on we will consider only complete graphs.

Counting Hamilton circuits
• how many Hamilton circuits, starting at a given vertex
• does a complete graph of 5 vertices (A, B, C, D, E) have?
• let's count them, starting (and ending) with A

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:

 A complete graph of n vertices has (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?··

Listing Hamilton circuits

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:

ABDCA
ABCDA