Unfortunately, there are no
counterparts to Euler’s theorems that tell us, in general, whether or not a graph has
a Hamilton Circuit.Example 1: Find both an Euler & Hamilton circuit for this graph.
Example 2: Find both an Euler & Hamilton circuit for this graph.
Sometimes there are situations where the following theorem will help us determine that a graph does have a Hamilton circuit.
/
2 vertices, then the graph has a Hamilton circuit. Recall that
two vertices are ADJACENT if there is an edge connecting them.Example 1:
Example 2:
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)! / 2Hamilton circuits.*distinct*
In problems involving Hamilton circuits, there
are often many seemingly equivalent routes. The most important class of problems solved
via Hamilton circuits is actually The Traveling Salesman Problem (TSP) |