Skip to ContentGo to accessibility pageKeyboard shortcuts menu
OpenStax Logo
Contemporary Mathematics

12.8 Hamilton Paths

Contemporary Mathematics12.8 Hamilton Paths

Menu
Table of contents
  1. Preface
  2. 1 Sets
    1. Introduction
    2. 1.1 Basic Set Concepts
    3. 1.2 Subsets
    4. 1.3 Understanding Venn Diagrams
    5. 1.4 Set Operations with Two Sets
    6. 1.5 Set Operations with Three Sets
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  3. 2 Logic
    1. Introduction
    2. 2.1 Statements and Quantifiers
    3. 2.2 Compound Statements
    4. 2.3 Constructing Truth Tables
    5. 2.4 Truth Tables for the Conditional and Biconditional
    6. 2.5 Equivalent Statements
    7. 2.6 De Morgan’s Laws
    8. 2.7 Logical Arguments
    9. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Projects
      5. Chapter Review
      6. Chapter Test
  4. 3 Real Number Systems and Number Theory
    1. Introduction
    2. 3.1 Prime and Composite Numbers
    3. 3.2 The Integers
    4. 3.3 Order of Operations
    5. 3.4 Rational Numbers
    6. 3.5 Irrational Numbers
    7. 3.6 Real Numbers
    8. 3.7 Clock Arithmetic
    9. 3.8 Exponents
    10. 3.9 Scientific Notation
    11. 3.10 Arithmetic Sequences
    12. 3.11 Geometric Sequences
    13. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  5. 4 Number Representation and Calculation
    1. Introduction
    2. 4.1 Hindu-Arabic Positional System
    3. 4.2 Early Numeration Systems
    4. 4.3 Converting with Base Systems
    5. 4.4 Addition and Subtraction in Base Systems
    6. 4.5 Multiplication and Division in Base Systems
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Projects
      5. Chapter Review
      6. Chapter Test
  6. 5 Algebra
    1. Introduction
    2. 5.1 Algebraic Expressions
    3. 5.2 Linear Equations in One Variable with Applications
    4. 5.3 Linear Inequalities in One Variable with Applications
    5. 5.4 Ratios and Proportions
    6. 5.5 Graphing Linear Equations and Inequalities
    7. 5.6 Quadratic Equations with Two Variables with Applications
    8. 5.7 Functions
    9. 5.8 Graphing Functions
    10. 5.9 Systems of Linear Equations in Two Variables
    11. 5.10 Systems of Linear Inequalities in Two Variables
    12. 5.11 Linear Programming
    13. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  7. 6 Money Management
    1. Introduction
    2. 6.1 Understanding Percent
    3. 6.2 Discounts, Markups, and Sales Tax
    4. 6.3 Simple Interest
    5. 6.4 Compound Interest
    6. 6.5 Making a Personal Budget
    7. 6.6 Methods of Savings
    8. 6.7 Investments
    9. 6.8 The Basics of Loans
    10. 6.9 Understanding Student Loans
    11. 6.10 Credit Cards
    12. 6.11 Buying or Leasing a Car
    13. 6.12 Renting and Homeownership
    14. 6.13 Income Tax
    15. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  8. 7 Probability
    1. Introduction
    2. 7.1 The Multiplication Rule for Counting
    3. 7.2 Permutations
    4. 7.3 Combinations
    5. 7.4 Tree Diagrams, Tables, and Outcomes
    6. 7.5 Basic Concepts of Probability
    7. 7.6 Probability with Permutations and Combinations
    8. 7.7 What Are the Odds?
    9. 7.8 The Addition Rule for Probability
    10. 7.9 Conditional Probability and the Multiplication Rule
    11. 7.10 The Binomial Distribution
    12. 7.11 Expected Value
    13. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Formula Review
      4. Projects
      5. Chapter Review
      6. Chapter Test
  9. 8 Statistics
    1. Introduction
    2. 8.1 Gathering and Organizing Data
    3. 8.2 Visualizing Data
    4. 8.3 Mean, Median and Mode
    5. 8.4 Range and Standard Deviation
    6. 8.5 Percentiles
    7. 8.6 The Normal Distribution
    8. 8.7 Applications of the Normal Distribution
    9. 8.8 Scatter Plots, Correlation, and Regression Lines
    10. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  10. 9 Metric Measurement
    1. Introduction
    2. 9.1 The Metric System
    3. 9.2 Measuring Area
    4. 9.3 Measuring Volume
    5. 9.4 Measuring Weight
    6. 9.5 Measuring Temperature
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  11. 10 Geometry
    1. Introduction
    2. 10.1 Points, Lines, and Planes
    3. 10.2 Angles
    4. 10.3 Triangles
    5. 10.4 Polygons, Perimeter, and Circumference
    6. 10.5 Tessellations
    7. 10.6 Area
    8. 10.7 Volume and Surface Area
    9. 10.8 Right Triangle Trigonometry
    10. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  12. 11 Voting and Apportionment
    1. Introduction
    2. 11.1 Voting Methods
    3. 11.2 Fairness in Voting Methods
    4. 11.3 Standard Divisors, Standard Quotas, and the Apportionment Problem
    5. 11.4 Apportionment Methods
    6. 11.5 Fairness in Apportionment Methods
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  13. 12 Graph Theory
    1. Introduction
    2. 12.1 Graph Basics
    3. 12.2 Graph Structures
    4. 12.3 Comparing Graphs
    5. 12.4 Navigating Graphs
    6. 12.5 Euler Circuits
    7. 12.6 Euler Trails
    8. 12.7 Hamilton Cycles
    9. 12.8 Hamilton Paths
    10. 12.9 Traveling Salesperson Problem
    11. 12.10 Trees
    12. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  14. 13 Math and...
    1. Introduction
    2. 13.1 Math and Art
    3. 13.2 Math and the Environment
    4. 13.3 Math and Medicine
    5. 13.4 Math and Music
    6. 13.5 Math and Sports
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Formula Review
      4. Projects
      5. Chapter Review
      6. Chapter Test
  15. A | Co-Req Appendix: Integer Powers of 10
  16. Answer Key
    1. Chapter 1
    2. Chapter 2
    3. Chapter 3
    4. Chapter 4
    5. Chapter 5
    6. Chapter 6
    7. Chapter 7
    8. Chapter 8
    9. Chapter 9
    10. Chapter 10
    11. Chapter 11
    12. Chapter 12
    13. Chapter 13
  17. Index
A group of children getting on a school bus.
Figure 12.190 A school bus picks up children along a planned route. (credit: “Kids at School Bus Stop” by Ty Hatch/Flickr, CC BY 2.0)

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.

In the United States, school buses carry 25 million children between school and home every day. The total distance they travel is around 6 billion kilometers per year. In the city of Boston, Massachusetts, the 2016 budget for running those buses was $120 million dollars. In 2017, the city held a competition to find ways to cut costs and the Quantum Team from the MIT Operations Research Center came to the rescue, using a computer algorithm to identify the most efficient and least costly routes, which saved the city of Boston $5 million each year and even reduced daily CO2 emissions by 9,000 kilograms! (This U.S. city put an algorithm in charge of its school bus routes and saved $5 million, Sean Fleming, World Economic Forum)

The problem the Quantum Team tackled involves graph theory. Imagine a graph in which vertices are the bus depot, the school, and the bus stops along a particular route. The bus must start at the depot, visit every stop exactly once, and end at the school. The route is a special kind of path that visits every vertex exactly once. Can you guess what those paths are called?

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

Three concentric ovals represent paths, trails, and walks. The first (inner) oval labeled paths reads, no repeated edges or vertices. The second oval labeled trails reads, no repeated edges. The third oval is labeled walks.
Figure 12.191 Walks, Trails, and Paths
Two graphs. Each graph has five vertices: A, B, C, D, and E. In the first graph, directed edges flow from A to B, B to C, and C to E. In the second graph, directed edges flow from A to B, B to C, C to D, and D to E.
Figure 12.192 Path or Hamilton Path?

Example 12.38

Identifying Hamilton Paths

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

Graph Q has two overlapping quadrilaterals. The vertices of the outer quadrilateral are a, c, h, and f. The vertices of the inner quadrilateral are d, b, e, and g. The vertex, d rests on the edge a f. The vertex, b rests on the edge a c. The vertex, e rests on the edge c h. The vertex, g rests on the edge h f.
Figure 12.193 Graph Q
  1. adbcegf
  2. cbehgfda
  3. hegdbegfdabc

Your Turn 12.38

Use the graphs to determine if the given sequence of vertices represents a Hamilton path or not.
Two graphs are labeled graph A and graph K. Graph A has five vertices: b, c, d, e, and f. Edges connect b c, c f, b d, b e, d e, and e f. Graph K has five vertices: m, n, o, p, and q. Edges connect m n, n o, n q, q o, o p, n p, and m p.
Figure 12.194 Graphs A and K
1.
Graph A, bcdef
2.
Graph A, befcbd
3.
Graph K, nqopm

Checkpoint

TIP! Since a Hamilton path visits each vertex exactly once, it must have the same number of vertices listed as appear in the graph.

Finding Hamilton Paths

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

A map of aquarium exhibits. The vertices are labeled A to S. The entrance is at the bottom.
Figure 12.195 Map of Aquarium Exhibits

Figure 12.196 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.

A graph has 19 vertices labeled from A to S. Edges connect A C, C B, B S, B E, S E, E D, A D, D F, A F, D G, G E, F I, F J, I J, I P, J P, J K, P O, G H, H L, L N, N K, K H, H N, L K, L M, N M, O Q, M Q, Q R, M R, and S R.
Figure 12.196 Graph of Aquarium

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.197. If R is not chosen next, that will cause a problem later on. Do you see what it is?

A graph has 19 vertices labeled from A to S. Edges connect A C, C B, B S, B E, S E, E D, A D, D F, A F, D G, G E, F I, F J, I J, I P, J P, J K, P O, G H, H L, L N, N K, K H, H N, L K, L M, N M, O Q, M Q, Q R, M R, and S R. The edges, O Q, Q M, M R, M L, and M N are directed. A question mark is above M.
Figure 12.197 Choosing Vertex L, N, or R

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.198, 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?

A graph has 19 vertices labeled from A to S. Edges connect A C, C B, B S, B E, S E, E D, A D, D F, A F, D G, G E, F I, F J, I J, I P, J P, J K, P O, G H, H L, L N, N K, K H, H N, L K, L M, N M, O Q, M Q, Q R, M R, and S R. The edges, O Q, Q M, M R, R S, S B, and S E are directed. A question mark is above S.
Figure 12.198 Choosing Vertex B or E

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.199. After G, you must visit H, but should you visit K or L after that?

A graph has 19 vertices labeled from A to S. Edges connect A C, C B, B S, B E, S E, E D, A D, D F, A F, D G, G E, F I, F J, I J, I P, J P, J K, P O, G H, H L, L N, N K, K H, H N, L K, L M, N M, O Q, M Q, Q R, M R, and S R. The edges, O Q, Q M, M R, R S, S B, B E, E G, G H, H L, and H K are directed. A question mark is above H.
Figure 12.199 Choose Vertex L or K

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.200. Should you choose F, I, or P next?

A graph has 19 vertices labeled from A to S. Edges connect A C, C B, B S, B E, S E, E D, A D, D F, A F, D G, G E, F I, F J, I J, I P, J P, J K, P O, G H, H L, L N, N K, K H, H N L K, L M, N M, O Q, M Q, Q R, M R, and S R. The edges, O Q, Q M, M R, R S, S B, B E, E G, G H, H L, L N, N K, K J, J F, J I, and J P are directed. A question mark is above J.
Figure 12.200 Choose Vertex F, I, or P

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.201.

A graph has 19 vertices labeled from A to S. Edges connect A C, C B, B S, B E, S E, E D, A D, D F, A F, D G, G E, F I, F J, I J, I P, J P, J K, P O, G H, H L, L N, N K, K H, H N, L K, L M, N M, O Q, M Q, Q R, M R, and SR. The edges, O Q, Q M, M R, R S, S B, B E, E G, G H, H L, L N, N K, K J, J P, P I, I F, F A, and F D are directed. A question mark is above F.
Figure 12.201 Choose Vertex A or D

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.202.

A graph has 19 vertices labeled from A to S. Edges connect A C, C B, B S, B E, S E, E D, A D, D F, A F, D G, G E, F I, F J, I J, I P, J P, J K, P O, G H, H L, L N, N K, K H, H N, L K, L M, N M, O Q, M Q, Q R, M R, and S R. The edges, O Q, Q M, M R, R S, S B, B E, E G, G H, H L, L N, N K, K J, J P, P I, I F, F D, D A, and A C are directed.
Figure 12.202 Complete Hamilton Path from O to C

So, one Hamilton path that begins at O and ends at C is OQMRSBEGHLNKJPIFDAC.

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.

Example 12.39

Finding a Hamilton Path

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

Graph G has six vertices. The vertices are C, A, B, F, D, and E. Edges connect C A, A B, A F, B F, F D, F E, and D E.
Figure 12.203 Graph G

Your Turn 12.39

1.
Use Figure 12.253 to find a Hamilton path between vertices C and E.

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.203. 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.204.

A graph represents the bridge between green and red apples. The graph has six vertices. The vertices are C, A, B, F, D, and E. Edges connect A B, A F, B F, F D, F E, and D E. Green apples: C. Red apples: A, B, F, D, and E. A bridge is between C and A.
Figure 12.204 Bridge between Red and Green Apples

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.

Example 12.40

Finding a Hamilton Path If One Exists

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

Four graphs. Graph A has two overlapping quadrilaterals, s t u v and w x y z. An edge connects w to u. Graph B has two overlapping quadrilaterals, s t z y, and r v w x. A vertex, u is at the center of r v and t z. Graph C has six vertices. Edges connect s t, t v, v w, w x, x u, w u, u s, and u t. Graph D has 10 vertices. Edges from t lead to x, r, s, u, and q. Edges from x lead to v, w, y, and z. Edges connect r s, u q, v w, and y z.
Figure 12.205 Graphs A, B, C, and D

Your Turn 12.40

Use Graph L to find a Hamilton path between each pair of vertices or indicate that there isn’t one.
Graph L has two quadrilaterals. The vertices of the first quadrilateral are m, o, n, and p. The vertices of the second quadrilateral are q, r, s, and t. Other edges connect m to n, n to q, and q to s.
Figure 12.211 Graph L
1.
p to r
2.
m to p
3.
o to q

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.

Scenario Diagram
Scenario 1 If an edge ab is a bridge, then there is no Hamilton path between a pair of vertices that are on the same side of edge ab. We saw this in Graph A of Example 12.40.
A graph has nine vertices labeled a to i. The edges connect c f, f a, a c, a d, d c, a b, b e, e h, h i, I g, and g b.
No Hamilton path between any two vertices in the component
{a, c, d, f}.
No Hamilton path between any two vertices in {b, e, h, g, i}.
Scenario 2 If an edge ab is a bridge with at least three components on each side, then there is no Hamilton path beginning or ending at a or b. We saw this in Graph D of Example 12.40.
A graph has six vertices labeled a to f. The edges connect a b, b e, b f, e f, a d, a c, and c d.

No Hamilton path beginning or ending at a or b.

Scenario 3 If a graph is composed of two cycles joined only at a single vertex p, and v is any vertex that is NOT adjacent to p, then there are no Hamilton paths beginning or ending at p. We saw this in Graph B of Example 12.40.
A graph has 8 vertices labeled p to w. The edges connect s r, r q, q p, p s, p w, w v, v, u t, and t p.
No Hamilton path can be formed starting or ending at vertices, r, v, or u because they are not adjacent to p.
Table 12.10 Some Impossible Hamilton Paths

Checkpoint

There are also many other situations in which a Hamilton path is not possible. These are just a few that you will encounter.

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.

Example 12.41

Distinguishing between Hamilton Path and Euler Trail

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

Three graphs. Graph A has five vertices: a, b, c, d, and e. Edges connect a b, b c, c d, d e, e a, and e b. Graph F has five vertices: f, g, h, i, and j. Edges connect f g, g h, h i, i j, j f, f i, f h, j g, and j h. Graph K has five vertices: k, l, m, n, and o. Edges connect k l, l m, m n, and n o.
Figure 12.212 Graphs A, F, and K
  1. Graph A, ebaedcb
  2. Graph F, fgjhi
  3. Graph K, klmno

Your Turn 12.41

Use Figure 12.262 to determine if the given sequence of vertices is a Hamilton path, an Euler trail, both, or neither.
1.
Graph A, abedc
2.
Graph F, ghijhfgjfi
3.
Graph K, onml

WORK IT OUT

As we saw in Figure 12.147, the Emerald City lies at the center of the Magical Land of Oz, with Gillikin Country to the north, Winkie Country to the east, Munchkin Country to the west, and Quadling Country to the south. Munchkin Country and Winkie Country each shares a border with Gillikin Country and Quadling Country. Let’s apply graph theory to Dorothy’s famous journey through Oz one more time!

Draw a graph in which each vertex is one of the regions of Oz. Is there a Hamilton path that Dorothy could follow, instead of the yellow brick road, to lead her from the land of the Munchkins, through all the regions of Oz exactly once, and end in the Emerald City? If so, what might it be? Compare your results with those of a classmate.

Check Your Understanding

For the following exercises, fill in the blank with the same as or different from to make the statement true.
67.
Unlike in a Hamilton cycle, the vertex where the Hamilton path begins is _________ the vertex where the Hamilton path ends.
68.
If a sequence of vertices represents a Hamilton path, the number of vertices listed should be _______ the number of vertices in the whole graph.
69.
To determine if a graph has a Hamilton path, use a method that is _________ the method used to determine if a graph has an Euler trail.
70.
If a graph with a bridge has a Hamilton path, the starting vertex should be on the side of the bridge that is ________ the side of the bridge with the ending vertex.
71.
A path between two vertices of a graph that visits each vertex of the graph exactly once is called an Euler path.
  1. True
  2. False
72.
Any graph that has exactly two vertices of odd degree has a Hamilton path.
  1. True
  2. False
73.
If a graph is composed of two cycles joined only at a single vertex p, then no Hamilton path can be formed starting or ending at any vertex that is adjacent to p.
  1. True
  2. False
74.
If an edge ab is a bridge with at least three components on each side, then there is no Hamilton path between vertex a and any vertex on the other side of edge ab.
  1. True
  2. False

Section 12.8 Exercises

For the following exercises, use the figure to determine whether the sequence of vertices in the given graph is a Hamilton path, an Euler trail, both, or neither.
Three graphs. Graph G has six vertices: c, d, e, b, f, and g. Edges connect c d, d e, e g, d g, d f, b f, b g, c f, and f g. Graph N has six vertices: h, i, n, k, j, and m. Edges connect h i, i n, n k, i k, i j, k j, k m, m j, and j h. Graph W has seven vertices: t, s, r, o, q, v, and w. Edges connect t o, t s, s r, r w, q o, q v, and w v.
1.
Graph G: fbgedc
2.
Graph G: gbfcde
3.
Graph G: fbgdfcdeg
4.
Graph W: vwrstoq
5.
Graph W: srwvqot
6.
Graph N: hiknjh
7.
Graph N: nihjm
8.
Graph N: mjhiknijk
For the following exercises, use the figure to explain why the given sequence of vertices does not represent a Hamilton path.
Four graphs. Graph A has two overlapping quadrilaterals, s t u v and w x y z. An edge connects w to u. Graph B has two overlapping quadrilaterals, s t z y, and r v w x. A vertex, u is at the center of r v and t z. Graph C has six vertices. Edges connect s t, t v, v w, w x, x u, w u, u s, and u t. Graph D has 10 vertices. Edges from t lead to x, r, s, u, and q. Edges from x lead to v, w, y, and z. Edges connect r s, u q, v w, and y z.
9.
Graph A: tsvuxwyz
10.
Graph B: wxruzystuv
11.
Graph C: suwvt
12.
Graph D: rtqutxvwxzy
For the following exercises, use the figure to find a path that fits the description or indicate which scenario from the figure makes it impossible.
Two graphs are labeled graph H and graph Q. Graph H has seven vertices labeled a to g. Edges connect a b, a e, b d e d, d c, d f, f g, and c g. Graph Q has seven vertices labeled h to n. Edges connect h i, h j, I j, I k, k m, m n, m l, and l n.
13.
A Hamilton path in Graph H that begins at vertex c and ends at vertex e.
14.
A Hamilton path in Graph Q that begins at vertex n and ends at vertex h.
15.
A Hamilton path in Graph H that begins at vertex c and ends at vertex g.
16.
A Hamilton path in Graph Q that begins at vertex m and ends at vertex j.
17.
A Hamilton path in Graph H that begins at vertex g.
18.
A Hamilton path in Graph Q that begins at vertex i.
19.
A path between n and j in Graph Q that is NOT a Hamilton path, and explain why it is not a Hamilton path.
20.
A path between a and c in Graph H that is NOT a Hamilton path, and explain why it is not a Hamilton path.
21.
In chess, a knight can move in any direction, but it must move two spaces then turn and move one more space. The eight possible moves a knight can make from a given space are shown in the figure.
A 5 by 5 square chess board. A knight is at the center of the board. The knight moves in an L-shape and it is indicated by 8 arrows. It moves either two steps  left or right followed by one step up or down, or two steps up or down followed by one step on the left or right.
A knight’s tour is a sequence of moves by a knight on a chessboard (of any size) such that the knight visits every square exactly once. If the knight’s tour brings the knight back to its starting position on the board, it is called a closed knight’s tour. Otherwise, it is called an open knight’s tour. Determine if the Knight’s tour shown in the figure is a Hamilton path, an Euler trail, or both, for the graph of all possible knight moves on an eight-by-eight chess board in which the vertices are spaces on the board and the edges indicate that the knight can move directly from one space to the other. Explain your reasoning.
A graph represents a knight's moves on an 8 by 8 chessboard. The knight moves in an L-shape. The movement of the knight inside the board is mapped and connected with edges.
Recall from the section Euler Circuits, as part of the Camp Woebegone Olympics, there is a canoeing race with a checkpoint on each of the 11 different streams as shown in the figure. The contestants must visit each checkpoint.
A map of canoe event checkpoints. The map has vertices labeled from A to K. The start point is also marked on the map.
22.
Draw a graph in which the vertices represent checkpoints, and an edge indicates that it is possible to travel from one checkpoint to the next without passing through another checkpoint.
23.
Find a Hamilton path beginning at vertex A and ending at vertex E.
24.
What does this Hamilton path represent in the context of the race?
The figure shows a map of zoo exhibits A through P. Use it to answer each question.
A map of zoo exhibits. The vertices are labeled A to P. The entrance is at the bottom.
25.
Draw a graph to represent the routes through the zoo in which the edges represent walkways and the vertices represent exhibits. Two vertices are connected if a person can walk between the exhibits they represent without passing another exhibit.
26.
Use the graph you created to find a route that begins at exhibit M, ends at exhibit J, and visits each exhibit exactly once.
Citation/Attribution

Want to cite, share, or modify this book? This book uses the Creative Commons Attribution License and you must attribute OpenStax.

Attribution information
  • If you are redistributing all or part of this book in a print format, then you must include on every physical page the following attribution:
    Access for free at https://openstax.org/books/contemporary-mathematics/pages/1-introduction
  • If you are redistributing all or part of this book in a digital format, then you must include on every digital page view the following attribution:
    Access for free at https://openstax.org/books/contemporary-mathematics/pages/1-introduction
Citation information

© Apr 17, 2023 OpenStax. Textbook content produced by OpenStax is licensed under a Creative Commons Attribution License . The OpenStax name, OpenStax logo, OpenStax book covers, OpenStax CNX name, and OpenStax CNX logo are not subject to the Creative Commons license and may not be reproduced without the prior and express written consent of Rice University.