maths.free › Combinatorics & Graph Theory › 12. Graph Theory › Hamilton Paths

Hamilton Paths

Describe and identify 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 . 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. shows a path from vertex A to vertex E and a Hamilton path from vertex A to vertex E.

Identifying Hamilton Paths

Try it.

Which of the following sequences of vertices is a Hamilton path for Graph Q in ?

  1. a → d → b → c → e → g → f
  2. c → b → e → h → g → f → d → a
  3. h → e → g → d → b → e → g → f → d → a → b → c
Solution

Sequence 1 is a path, because it is a walk that doesn’t repeat any vertices or edges, but not a Hamilton path because it skips vertex h. Sequence 2 is a path that visits each vertex exactly once; so, it is a Hamilton path. Sequence 3 is a walk, but it is not a path because it visits vertices g, e, and b each more than once; so, it cannot be a Hamilton path. So, we can see that only sequence 2 is a Hamilton path.

Condensed — the full section is in OpenStax Contemporary Mathematics.

Existence of a Hamilton Path

It turns out that there is no Hamilton path between vertices A and E in Graph G in . 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 .

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 .

Condensed — the full section is in OpenStax Contemporary Mathematics.

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.

Distinguishing between Hamilton Path and Euler Trail

Try it.

Use to determine if the given sequence of vertices is a Hamilton path, an Euler trail, both, or neither.

  1. Graph A, e → b → a → e → d → c → b
  2. Graph F, f → g → j → h → i
  3. Graph K, k → l → m → n → o
Solution
  1. Since the sequence covers every edge once but visits vertices more than once, it is only an Euler trail.
  2. Since the sequence visits every vertex exactly once but skips some edges, it is only a Hamilton path.
  3. Since the sequence visits each edge and each vertex exactly once, it is both an Euler trail and a Hamilton path.

Practice (4)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

  1. Which of the following sequences of vertices is a Hamilton path for Graph Q in ?

    1. a → d → b → c → e → g → f
    2. c → b → e → h → g → f → d → a
    3. h → e → g → d → b → e → g → f → d → a → b → c
    Жауап

    Sequence 1 is a path, because it is a walk that doesn’t repeat any vertices or edges, but not a Hamilton path because it skips vertex h. Sequence 2 is a path that visits each vertex exactly once; so, it is a Hamilton path. Sequence 3 is a walk, but it is not a path because it visits vertices g, e, and b each more than once; so, it cannot be a Hamilton path. So, we can see that only sequence 2 is a Hamilton path.

  2. Use to find a Hamilton path between vertices C and D.

    Жауап

    If we start at vertex C, A must be next. Then we must choose between B and F. If we choose F, we will have to backtrack to get to include B; so, we must choose B. Once we choose B, we must choose F next. After F, we choose E, because we want to end at D. So, a Hamilton path between C and D is C → A → B → F → E → D.

  3. Find a Hamilton path from vertex s to vertex v for each graph in or indicate that there is none.

    Жауап

    Graph A: Edge uw is a bridge connecting component {s, t, u, v} to the component {w, x, y, z}. There is no Hamilton path from vertex s to vertex v because they would be part of the same component if the bridge uw were removed.

    Graph B: There are no bridges in Graph B. The only method we have to determine if a Hamilton path from vertex s to vertex v exists is to try every possibility. From vertex s, we can visit either vertex y or vertex t. We will try vertex y first and then come back to see what happens with vertex t. After visiting y, we must visit z and then u, but then we have to decide between vertices r, t, and v next as shown in .

    Vertex v is not an option since we want to end at v. Vertex t is not an option since that would force us to go to visit s a second time. So, we must go to vertex r next. After vertex r, we must visit x, then w, then v, but we missed vertex t as shown in .

    Let’s go back to the beginning and choose t instead of y. After t, we must go to u and then we have a choice to make between r, v, and z as shown in .

    Vertex v is not an option since we want to end at v. Vertex z is not an option since that would force us to go y and then to visit s a second time. So, we must go to vertex r next. After r, we must go to x then w then v, where we have to stop even though we have missed vertices y and z, as shown in .

    So, we have tried every possible route and there are no Hamilton paths between s and v in Graph B.

    Graph C: In Graph C, there is a Hamilton path, s → t → u → x → w → v.

    Graph D: In Graph D, there is a bridge, tx, which would form components {r, s, t, u, q} and {v, w, x, y, z} if it were removed. Since s and v would be in different components, it is possible there is a Hamilton path between them. The only way to know is to try all possibilities. If we begin at s, we can go to r then t, or we can go directly to t, either way, we have a problem as you can see in .

    If we visit all the vertices in the component {r, s, t, u, q}, we will have to visit t a second time in order to cross the bridge. If we visit t only once, we have to skip some of the vertices. So, there is no Hamilton path between s and v.

  4. Use to determine if the given sequence of vertices is a Hamilton path, an Euler trail, both, or neither.

    1. Graph A, e → b → a → e → d → c → b
    2. Graph F, f → g → j → h → i
    3. Graph K, k → l → m → n → o
    Жауап
    1. Since the sequence covers every edge once but visits vertices more than once, it is only an Euler trail.
    2. Since the sequence visits every vertex exactly once but skips some edges, it is only a Hamilton path.
    3. Since the sequence visits each edge and each vertex exactly once, it is both an Euler trail and a Hamilton path.

Symbols used here

i
imaginary unit
i² = −1.
n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
\prod_{k=1}^{n} a_k
product
Multiply a_k for k = 1 up to n.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.

How to: Hamilton Paths

  1. Describe and identify Hamilton paths.
  2. Evaluate Hamilton paths in real-world applications.
  3. Distinguish between Hamilton paths and Euler trails.
  4. Graph
  5. Graph
  6. Graph
  7. Since the sequence covers every edge once but visits vertices more than once, it is only an Euler trail.
  8. Since the sequence visits every vertex exactly once but skips some edges, it is only a Hamilton path.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Өзүңүздүн аракетиңизди көрүңүз

Parts of this page are adapted from OpenStax Contemporary Mathematics (CC BY-NC-SA 4.0). Condensed and re-explained here; errors are ours.

Кээ бирлери Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs