12.8 Hamilton Paths

Learning Objectives

After completing this section, you should be able to:

1. Describe and identify Hamilton paths.
2. Evaluate Hamilton paths in real-world applications.
3. Distinguish between Hamilton paths and Euler trails.

Hamilton Paths

Just as circuits that visit each vertex in a graph exactly once are called Hamilton cycles (or Hamilton circuits), paths that visit each vertex on a graph exactly once are called Hamilton paths. As we explore Hamilton paths, you might find it helpful to refresh your memory about the relationships between walks, trails, and paths by looking at Figure 12.166. We know that paths are walks that don’t repeat any vertices or edges. So, a Hamilton path visits every vertex without repeating any vertices or edges. Figure 12.167 shows a path from vertex A to vertex E and a Hamilton path from vertex A to vertex E.

Finding Hamilton Paths

Suppose you were visiting an aquarium with some friends. The map of the aquarium is given in Figure 12.169. The letters represent the exhibits.

Figure 12.170 shows a graph of the aquarium in which each vertex represents an exhibit and each edge is a route between the pair of exhibits that doesn’t bypass another exhibit.

Let’s see if we can plan a tour of the exhibits that visits each exhibit exactly once, beginning at exhibit O and ending at exhibit C. Suppose that, after exhibit O, we plan to visit exhibit Q and then exhibit M. After M, should we plan to visit N, L, or R? Take a look at Figure 12.171. If R is not chosen next, that will cause a problem later on. Do you see what it is?

If L or N is chosen next, the only way to get to R later will be to go from S to R, and then we will not be able to continue without repeating a vertex. So, we will pick R next, and then the only option is S. After S we have another choice to make. As shown in Figure 12.172, the next choice is between B and E. Keeping in mind that the goal is to end at C, which would be the better choice?

If you said vertex B, you are right! Otherwise, we will not be able to visit B later. After B, the only option is E. Then we can choose either D or G. Either will work fine. Let’s choose G as shown in Figure 12.173. After G, you must visit H, but should you visit K or L after that?

If you said to go to vertex L next, you are right! Otherwise, it will be impossible to visit N without repeating a vertex. So, next is L, then N, then K, and then at J you have another decision to make we can see in Figure 12.174. Should you choose F, I, or P next?

If you said P, you are right! If you choose either of the other two vertices, you will not be able to visit P later without passing through another vertex twice. Once P is chosen, vertex I must be next followed by F. Then you have to choose between A and D as shown in Figure 12.175.

In this case, we must go to D then to A so that we can visit C without backtracking. The complete Hamilton path is shown in Figure 12.176.

So, one Hamilton path that begins at O and ends at C is O → Q → M → R → S → B → E → G → H → L → N → K → J → P → I → F → D → A → C.

There is no set sequence of steps that can be used to find a Hamilton path if it exists, but it does help to keep in mind where we are headed and avoid choices that will make returning to a particular vertex impossible without repeating vertices. Let’s practice finding Hamilton paths.

Existence of a Hamilton Path

It turns out that there is no Hamilton path between vertices A and E in Graph G in Figure 12.177. To understand why, let’s imagine there is a red apple tree on one side of a bridge and a green apple tree on the other side of the bridge. Now suppose someone asked you to pick up all the fallen apples under each tree without crossing the bridge more than once, and making sure that the first apple you pick up and the last apple you pick up are both red. You would say, that is impossible! To have the first and last apple be red would either require leaving the green apples on the ground or crossing the bridge twice.

Let’s see how this relates to finding a Hamilton path between A and E in Graph G. The edge AC is a bridge because, if it were removed, the graph would become disconnected with two components, the component {C} and the component {A, B, D, E, F}. So, we can think of the vertices A, B, D, E, and F as the red apples, vertex C as the green apple, and the edge AC is the bridge between them as in Figure 12.178.

The creation of a Hamilton path requires a visit to each vertex, just as picking up all the apples requires a visit to each apple. A and E are both red apples; so, a path from A to E would both start and end at a red apple, just as you were asked to do. And you wouldn’t be able to cross the bridge twice because that would mean visiting A twice, which is not allowed in a Hamilton path. So, it is impossible to find a Hamilton path from A to E just as it was impossible to pick up all the apples without crossing the bridge more than once. By the same reasoning, if a graph has a bridge, there will never be a Hamilton path that begins and ends on the same side of that bridge, meaning beginning and ending at vertices that would be in the same component if the bridge were removed from the graph.

There is not a short way to determine if there is a Hamilton path between two vertices on a graph that works in every situation. However, there are a few common situations that can help us to quickly determine that there is no Hamilton path. Some of these are listed in Table 12.10.

Hamilton Path or Euler Trail?

We learned in Euler Trails that an Euler trail visits each edge exactly once, whereas a Hamilton path visits each vertex exactly once. Let’s practice distinguishing between the two.

Key Terms

• Hamilton path

Key Concepts

• A Hamilton path visits every vertex exactly once.
• Some Hamilton paths are also Euler trails, but some are not.