12.7 Hamilton Cycles

Learning Objectives

After completing this section, you should be able to:

1. Describe and identify Hamilton cycles.
2. Compute the number of Hamilton cycles in a complete graph.
3. Apply and evaluate weighted graphs.

Hamilton’s Puzzle

Before we look at the solution to Hamilton's puzzle, let’s review some vocabulary we used in Figure 12.157. It will be helpful to remember that directed cycle is a type of circuit that doesn’t repeat any edges or vertices.

The goal of Hamilton's puzzle was to find a route along the edges of the dodecahedron, which visits each vertex exactly once. A dodecahedron is a three-dimensional space figure with faces that are all pentagons as we saw in Figure 12.156.

Since it is easier to visualize two dimensions rather than three, we will flatten out the dodecahedron and look at the edges and vertices on a flat surface. Graph A in Figure 12.158 shows a two-dimensional graph of the edges and vertices, and Graph B shows an untangled version of Graph A in which no edges are crossing. Graph B in Figure 12.158 is very similar to the design of the game board that Hamilton invented for his puzzle.

We can see that this is a planar graph because it can be “untangled.” In order to solve Hamilton’s puzzle, we need to find a circuit that visits every vertex once. A solution is shown in Figure 12.159.

A circuit that doesn’t repeat any vertices, like the one in Figure 12.159, is called a directed cycle. So, we can most accurately say that Hamilton’s puzzle asks us to find a directed cycle that visits every vertex in a graph exactly once. Because Hamilton created and solved this puzzle, these special circuits were named Hamilton cycles, or Hamilton circuits.

Hamilton Cycles vs. Euler Circuits

Let’s practice naming and identifying Hamilton cycles, as well as distinguishing them from Euler circuits. It is important to remember that Euler circuits visit all edges without repetition, while Hamilton cycles visit all vertices without repetition. Hamilton cycles are named by their vertices just like all circuits. An example is given in Figure 12.160.

Notice that the Hamilton cycle a → b → c → d for Graph Z in Figure 12.160 is NOT an Euler circuit, because it does not visit edge $\mathit{ac}$. Some Hamilton cycles are also Euler circuits while some are not, and some Euler circuits are Hamilton cycles while some are not.

Notice that the graph is a cycle. A cycle will always be Eulerian because all vertices are degree 2. Moreover, any circuit in the graph will always be both an Euler circuit and a Hamilton cycle. It is not always as easy to determine if a graph has a Hamilton cycle as it is to see that it has an Euler circuit, but there is a large group of graphs that we know will always have Hamilton cycles, the complete graphs. Since all vertices in a complete graph are adjacent, we can always find a directed cycle that visits all the vertices. For example, look at the directed six-cycle, n → o → p → q → r → s, in the complete graph with six vertices in Figure 12.162.

That is not the only directed six-cycle in the graph though. We could find another just be reversing the direction, and we could find even more by using different edges. So, how many Hamilton cycles are in a complete graph with $n$ vertices? Before we tackle this problem, let’s look at a shorthand notation that we use in mathematics which will be helpful to us.

Factorials

In many areas of mathematics, we must calculate products like $7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$ or $$11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$$, products that involve multiplying all the counting numbers from a particular number down to 1. Imagine that the product happened to be all the numbers from 100 down to 1. That’s a lot of writing! Instead of writing all of that out, mathematicians came up with a shorthand notation. For example, instead of $7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$, we write $7!$, which is read “7 factorial.” In other words, the product of all the counting numbers from $n$ down to 1 is called $n$ factorial and it is written $n!$

A common use for factorials is counting the number of ways to arrange objects. Suppose that there were three students, Aryana, Byron, and Carlos, who wanted to line up in a row. How many arrangements are possible? There are six possibilities: ABC, ACB, BAC, BCA, CAB, or CBA. Notice that there were three students being arranged, and the number of possible arrangements is three.

Counting Hamilton Cycles in Complete Graphs

Now, let’s get back to answering the question of how many Hamilton cycles are in a complete graph. In Table 12.8, we have drawn all the four cycles in a complete graph with four vertices. Remember, cycles can be named starting with any vertex in the cycle, but we will name them starting with vertex $a$.

Table 12.8 shows that there are three unique four-cycles in a complete graph with four vertices. Notice that there were two ways to name each cycle, one reading the vertices in a clockwise direction and one reading the vertices in a counterclockwise direction. This is important to us because we are interested in Hamilton cycles, which are directed cycles. Although the cycles (a, b, c, d) and (a, d, c, b) are the same cycle, the directed cycles, a → b → c → d → a and a → d → c → b → a, which travel the same route in reverse order are considered different directed cycles, as shown in Table 12.9.

The six directed four-cycles in Table 12.9 are the only distinct Hamilton cycles in a complete graph with four vertices. Six is also the number of ways to arrange the three letters b, c, and d. (Do you see why?) The number of ways to arrange three letters is $3!=3\cdot 2\cdot 1=6$. Similarly, the number of Hamilton cycles in a graph with five vertices is the number of ways to arrange four letters, which is $4!=4\cdot 3\cdot 2\cdot 1=24$. In general, to find the number of Hamilton cycles in a graph, we take one less than the number of vertices and find its factorial.

Weighted Graphs

Suppose that an officer in the U.S. Air Force who is stationed at Vandenberg Air Force base must drive to visit three other California Air Force bases before returning to Vandenberg. The officer needs to visit each base once. The vertices in the graph in Figure 12.164 represent the four U.S. Air Force bases, Vandenberg, Edwards, Los Angeles, and Beale. The edges are labeled to with the driving distance between each pair of cities.

The graph in Figure 12.164 is called a weighted graph, because each edge has been assigned a value or weight. The weights can represent quantities such as time, distance, money, or any quantity associated with the adjacent vertices joined by the edges. The total weight of any walk, trail, or path is the sum of the weights of the edges it visits.

Notice that the officer’s trip can be represented as a Hamilton cycle, because each of the four vertices in the graph is visited exactly once.

Key Terms

• Hamilton cycle, or Hamilton circuit
• $n$ factorial
• weighted graph
• total weight

Key Concepts

• A Hamilton cycle is a directed cycle, or circuit, that visits each vertex exactly once.
• Some Hamilton cycles are also Euler circuits, but some are not.
• Hamilton cycles that follow the same undirected cycle in the same direction are considered the same cycle even if they begin at a different vertex.
• The number of unique Hamilton cycles in a complete graph with n vertices is the same as the number of ways to arrange $n-1$ distinct objects.
• Weighted graphs have a value assigned to each edge, which can represent distance, time, money and other quantities.

Formulas

The number of ways to arrange $n$ distinct objects is $n!$.

The number of distinct Hamilton cycles in a complete graph with $n$ vertices is $\left(n-1\right)!$.