How many simple circuits are there in an undirected complete

How many simple circuits are there in an undirected complete graph? (Hint: assume that the circuit starts and ends at node A. The length of the cycle is between 3 and n).

Solution

by takimg undirected complete graph

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!