Example 1: Find both an Euler & Hamilton circuit for this graph.

Euler circuit solution
Hamilton circuit solution

Example 2: Find both an Euler & Hamilton circuit for this graph.

Euler circuit solution
Hamilton circuit solution

Sometimes there are situations where the following theorem will help us determine that a graph does have a Hamilton circuit.

Dirac’s Theorem
If each vertex of a connected graph with n vertices (where n> 3) is adjacent to at least n / 2 vertices, then the graph has a Hamilton circuit. Recall that two vertices are ADJACENT if there is an edge connecting them.

Example 1:

There are 7 vertices... half of 7 is 3.5.
Since each vertex is adjacent to at least 4 of the other vertices, this graph has a Hamilton circuit by Dirac’s Theorem.

Example 2:

There are 7 vertices... half of 7 is 3.5.
Vertex B is adjacent to only 2 of the other vertices; Dirac’s Theorem does not apply & we do not know if there is a Hamilton circuit.

A complete graph is one in which each vertex is connected to every other vertex by exactly each edge. A complete graph always satisfies the conditions of Dirac's Theorem. So, all complete graphs have Hamilton circuits.

More Properties of Complete Graphs

• Complete graphs have LOTS of Hamilton circuits!
• In a complete graph with N vertices, each vertex has degree N-1.
• The total number of edges in a complete graph is N(N-1)/2.
• A complete graph with N vertices has (N-1)! Hamilton circuits. Half of these are just exact reversals of the other half. When we don’t want to count exact reversals, we will use the term distinct. So, a complete graph with N vertices has (N-1)! / 2 distinct Hamilton circuits.

In problems involving Hamilton circuits, there are often many seemingly equivalent routes. The most important class of problems solved via Hamilton circuits is actually when the edges connecting vertices have different weights. (For instance, it might be less expensive to travel one edge rather than a different one or perhaps the distancd traveled is less.)

The Traveling Salesman Problem (TSP)
The problem of finding an optimal Hamilton Circuit in a complete weighted graph is often called the Traveling Salesman Problem, or TSP for short. We will study several algorithms for solving TSPs.

Back