6.2 Complete Graphs

Topics
Complete graphs
Counting Hamilton circuits
Listing Hamilton circuits



Complete graphs

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

Example:

From now on we will consider only complete graphs.


Counting Hamilton circuits
1st leg of trip
1st 2 legs 
1st 3 legs
1st 4 legs
all 5 legs
starting at A, 
4 ways to choose 2nd city
for each of the 
4 ways for leg 1, 
3 ways to choose 3rd city 
or each of the 
4 x 3 ways for legs 1 and 2,
2 ways to choose 4th city
for each of the
4 x 3 x 2 ways for legs 1, 2, 3, 
1 way to choose 5th city 
must come back to A
4 
possibilities 
4 x 3 = 12 
possibilities
4 x 3 x 2 = 24 
possibilities
4 x 3 x 2 x 1 = 24
possibilities
still 
4 x 3 x 2 x 1=
24 
possibilities
AB ABC ABCD ABCDE ABCDEA
ABCE ABCED ABCEDA
ABD ABDC ABDCE ABDCEA
ABDE ABDEC ABDECA
ABE ABEC ABECD ABECDA
ABED ABEDC ABEDCA
AC ACB ACBD ACBDE ACBDEA
ACBE ACBED ACBEDA
ACD ACDB ACDBE ACDBEA
ACDE ACDEB ACDEBA
ACE ACEB ACEBD ACEBDA
ACED ACEDB ACEDBA
AD ADB ADBC ADBCE ADBCEA
ADBE ADBEC ADBECA
ADC ADCB ADCBE ADCBEA
ADCE ADCEB ADCEBA
ADE ADEB ADEBC ADEBCA
ADEC ADECB ADECBA
AE AEB AEBC AEBCD AEBCDA
AEBD AEBDC AEBDCA
AEC AECB AECBD AECBDA
AECD AECDB AECDBA
AED AEDB AEDBC AEDBCA
AEDC AEDCB AEDCBA

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:

ADBCA
ABDCA
ABCDA
ADCBA
ACDBA
ACBDA

Voila! 3! = 6 of them!

But look!  The last three above are simply reverses of the first 3!