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

12.6 Euler Trails

Contemporary Mathematics12.6 Euler Trails

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 map of the United States shows the Pony Express mail route. The route began in St. Joseph, Missouri and traveled through Fort Kearney, Nebraska; Julesburg, Colorado; Fort Laramie, Wyoming; Fort Bridger, Wyoming; Salt Lake City, Utah; Fort Ruby, Nevada; Carson City, Nevada; and San Francisco, California.
Figure 12.149 The Pony Express mail route spanned from California to Missouri. (credit: “Map of Pony Express” by Nathan Hughes Hamiltonh/Flickr, CC BY 2.0)

Learning Objectives

After completing this section, you should be able to:

  1. Describe and identify Euler trails.
  2. Solve applications using Euler trails theorem.
  3. Identify bridges in a graph.
  4. Apply Fleury’s algorithm.
  5. Evaluate Euler trails in real-world applications.

We used Euler circuits to help us solve problems in which we needed a route that started and ended at the same place. In many applications, it is not necessary for the route to end where it began. In other words, we may not be looking at circuits, but trails, like the old Pony Express trail that led from Sacramento, California in the west to St. Joseph, Missouri in the east, never backtracking.

Euler Trails

If we need a trail that visits every edge in a graph, this would be called an Euler trail. Since trails are walks that do not repeat edges, an Euler trail visits every edge exactly once.

Example 12.29

Recognizing Euler Trails

Use Figure 12.150 to determine if each series of vertices represents a trail, an Euler trail, both, or neither. Explain your reasoning.

Graph H has 7 vertices labeled a to g. The edges connect a b, a d, b e, e d, d c, c f, f g, d g, and g e.
Figure 12.150 Graph H
  1. abegfcde
  2. abegfcdebadg
  3. gdabedcfge

Your Turn 12.29

Use the figure to determine if each sequence of vertices represents an Euler trail or not. If not, explain why.
Graph I has 8 vertices labeled a to h. The edges connect a b, b f, a d, f e, e d, d c, c g, g h, and e h.
Figure 12.151 Graph I
1.
efbadcghed
2.
dabfehgc
3.
dabefbedcghe

The Five Rooms Puzzle

Just as Euler determined that only graphs with vertices of even degree have Euler circuits, he also realized that the only vertices of odd degree in a graph with an Euler trail are the starting and ending vertices. For example, in Figure 12.150, Graph H has exactly two vertices of odd degree, vertex g and vertex e. Notice the Euler trail we saw in Excercise 3 of Example 12.29 began at vertex g and ended at vertex e.

This is consistent with what we learned about vertices off odd degree when we were studying Euler circuits. We saw that a vertex of odd degree couldn't exist in an Euler circuit as depicted in Figure 12.152. If it was a starting vertex, at some point we would leave the vertex and not be able to return without repeating an edge. If it was not a starting vertex, at some point we would return and not be able to leave without repeating an edge. Since the starting and ending vertices in an Euler trail are not the same, the start is a vertex we want to leave without returning, and the end is a vertex we want to return to and never leave. Those two vertices must have odd degree, but the others cannot.

Two illustrations. The first illustration shows a vertex, 3. Two arrows point to it and an arrow points away from it. The second illustration shows a vertex, 3. Two arrows point away from it and an arrow points to it.
Figure 12.152 A Vertex of Degree 3

Let’s use the Euler trail theorem to solve a puzzle so you can amaze your friends! This puzzle is called the “Five Rooms Puzzle.” Suppose that you were in a house with five rooms and the exterior. There is a doorway in every shared wall between any two rooms and between any room and the exterior as shown in Figure 12.153. Could you find a route through the house that passes through each doorway exactly once?

An illustration shows five rooms in a rectangle labeled f. The rooms are labeled a to e.
Figure 12.153 Five Rooms Puzzle

Let’s represent the puzzle with a graph in which vertices are rooms (or the exterior) and an edge indicates a door between two rooms as shown in Figure 12.154.

An illustration shows five rooms in a rectangle labeled f. An arrow from the illustration points to a graph with six vertices. In the illustration, the rooms are labeled a to e. The vertices are a to f. Edges interconnect all the vertices. In the graph, the vertices are labeled a to f. edges connect a b, a d, b d, b e, a c, c d, d e, c d, c f, d f, d e, and e f. Double curved edges connect a to f and b to f. Curved edges connect c to f and f to e.
Figure 12.154 Graph of Five Rooms Puzzle

To pass through each doorway exactly once means that we cross every edge in the graph exactly once. Since we have not been asked to start and end at the same position, but to visit each edge exactly once, we are looking for an Euler trail. Let’s check the degrees of the vertices.

A graph has six vertices a to f and their degrees are 5, 5, 4, 5, 4, and 9. Edges connect a b, a d, b d, b e, a c, c d, d e, c d, c f, d f, d e, and e f. Double curved edges connect a to f and b to f. Curved edges connect c to f and f to e.
Figure 12.155 Degrees of Vertices in Five Rooms Puzzle

Since there are more than two vertices of odd degree as shown in Figure 12.155, the graph of the five rooms puzzle contains no Euler path. Now you can amaze and astonish your friends!

Bridges and Local Bridges

Now that we know which graphs have Euler trails, let’s work on a method to find them. The method we will use involves identifying bridges in our graphs. A bridge is an edge which, if removed, increases the number of components in a graph. Bridges are often referred to as cut-edges. In Figure 12.156, there are several examples of bridges. Notice that an edge that is not part of a cycle is always a bridge, and an edge that is part of a cycle is never a bridge.

A graph has two triangles and one square. The first triangle has vertices, a, b, and c. The second triangle has vertices, g, k, and j. The square has the vertices, e, f, h, and i. An edge connects e and i. The bridges connect b f, c g, and d g.
Figure 12.156 Graph with Bridges

Edges bf, cg, and dg are “bridges”

The graph in Figure 12.156 is connected, which means it has exactly one component. Each time we remove one of the bridges from the graph the number of components increases by one as shown in Figure 12.157. If we remove all three, the resulting graph in Figure 12.157 has four components.

Four graphs. The first graph has two triangles and a square. The first triangle has vertices, a, b, and c. The second triangle has vertices, g, k, and j. The square has the vertices, e, f, h, and i. An edge connects e and i. The bridges connect b f, c g, and d g. The second graph is the same. The square is separated. The third graph shows the square and the triangles separated. The second triangle is connected to the vertex, d. In the fourth graph, the triangles, square, and the d vertex are separated.
Figure 12.157 Removing a Bridge Increases Number of Components

In sociology, bridges are a key part of social network analysis. Sociologists study two kinds of bridges: local bridges and regular bridges. Regular bridges are defined the same in sociology as in graph theory, but they are unusual when studying a large social network because it is very unlikely a group of individuals in a large social network has only one link to the rest of the network. On the other hand, a local bridge occurs much more frequently. A local bridge is a friendship between two individuals who have no other friends in common. If they lose touch, there is no single individual who can pass information between them. In graph theory, a local bridge is an edge between two vertices, which, when removed, increases the length of the shortest path between its vertices to more than two edges. In Figure 12.158, a local bridge between vertices b and e has been removed. As a result, the shortest path between b and e is bijke, which is four edges. On the other hand, if edge ab were removed, then there are still paths between a and b that cover only two edges, like aib.

Two graphs. The first graph shows a triangle, i a b resting on a square, a b d e, and another triangle, k e f resting on a square, e f g h. The squares have diagonal lines. Edges connect i j and j k. A bridge connects b e. The second graph shows a triangle, i a b resting on a square, a b d e, and another triangle, k e f resting on a square, e f g h. The squares have diagonal lines. Bridges connect i j and j k.
Figure 12.158 Removing a Local Bridge

The significance of a local bridge in sociology is that it is the shortest communication route between two groups of people. If the local bridge is removed, the flow of information from one group to another becomes more difficult. Let’s say that vertex b is Brielle and vertex e is Ella. Now, Brielle is less likely to hear about things like job opportunities, that Ella many know about. This is likely to impact Brielle as well as the friends of Brielle.

Example 12.30

Identifying Bridges and Local Bridges

Use the graph of a social network in Figure 12.159 to answer each question.

A graph with 23 vertices. The edges are as follows: a b, b c, h i, a d, b e, c e, h g, d e, e f, f g, d n, f j, f k, g k, j k, k u, j o, n m, m o, n p, n q, m q, q o, o r, u v, u w, u x, p q, q r, v w, w x, p s, q t, and s t.
Figure 12.159 Graph of a Social Network
  1. Identify any bridges.
  2. If all bridges were removed, how many components would there be in the resulting graph?
  3. Identify one local bridge.
  4. For the local bridge you identified in part 3, identify the shortest path between the vertices of the local bridge if the local bridge were removed.

Your Turn 12.30

1.
How many bridges and local bridges are in a complete graph with three or more vertices? Explain your reasoning.

Finding an Euler Trail with Fleury’s Algorithm

Now that we are familiar with bridges, we can use a technique called Fleury’s algorithm, which is a series of steps, or algorithm, used to find an Euler trail in any graph that has exactly two vertices of odd degree. Here are the steps involved in applying Fleury’s algorithm.

Here are the steps involved in applying Fleury’s algorithm.

Step 1: Begin at either of the two vertices of odd degree.

Step 2: Remove an edge between the vertex and any adjacent vertex that is NOT a bridge, unless there is no other choice, making a note of the edge you removed. Repeat this step until all edges are removed.

Step 3: Write out the Euler trail using the sequence of vertices and edges that you found. For example, if you removed ab, bc, cd, de, and ef, in that order, then the Euler trail is abcdef.

Figure 12.161 shows the steps to find an Euler trail in a graph using Fleury’s algorithm.

Eight graphs. Each graph has six vertices: t, u, v, w, x, and y. In the first graph, the edges are t u, u w, w y, y x, x v, v t, and v w. Text reads, start at odd degree. Choose direction. The edges flowing from t to u, v, and w are highlighted in blue. The second graph is the same as that of the first, with the edge, tv in dashed lines and labeled remove tv. The edges flowing from v to w and x are in blue. Text reads, then choose the direction. The third graph shows edges, t u, u w, w y, y x, x v, and v w. The edge, v w is in dashed lines and labeled remove v w. The edges from w to t and u are in blue and labeled then choose the direction. The edge from w to y is shown in red and labeled no. The fourth graph shows the edges, t u, u w, w y, y x, x v, and t w. The edge, w u is in dashed lines, and remove w u. The edge from w to y is in red and labeled do not remove bridge wy. The edge from u to t is in blue. The fifth graph shows the edge, t u, t w, w y, y x, and x v. The edge, u t is in dashed lines and labeled remove u t. The edge from t to w is in blue. The sixth graph shows the edge, t w, w y, y z, and x v. The edge, t w is in dashed lines and labeled remove t w. The edge from w to y is in blue. The seventh graph shows the edges, w y, y z, and x v. The edge, w y is in dashed lines and labeled remove w y. The edge from y to x is in blue. The eighth graph shows the edges, y x, and x v. The edge, y x is in dashed lines and labeled remove y x then x v. The edge from x to v is in blue.
Figure 12.161 Using Fleury’s Algorithm To Find Euler Trail

The Euler trail that was found in Figure 12.161 is tvwutwyxv.

Example 12.31

Finding an Euler Trail with Fleury’s Algorithm

Use Fleury’s Algorithm to find an Euler trail for Graph J in Figure 12.162.

Graph J has 9 vertices: a, b, c, d, e, f, g, h, and i. Edges connect a b, b d, d c, c a, b c, b f, e f, f g, g i, I h, and h e.
Figure 12.162 Graph J

Checkpoint

TIP! To avoid errors, count the number of edges in your graph and make sure thatyour Euler trail represents that number of edges.

Your Turn 12.31

Use Graph L to fill in the blanks to complete the steps in Fleury’s algorithm.
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.166 Graph L
1.
The two vertices that can be used as the starting vertex are ____ and s.
2.
If sq is the first edge removed, the three options for the second edge to be removed are qr, ___, and ___; however, ___ cannot be chosen because it is a ________________.
3.
If qr is the second edge removed, the next four edges to be removed must be ___, ___, ___, and ___, in that order.
4.
After qn is removed, the three options for the next edge to be removed are no, ___, and ___, however, ___ cannot be chosen because it is a _____________.
5.
If no is the next edge removed, the last four edges removed will be ___, ___, ___, and ___, in that order.
6.
The final Euler trail using the answers to parts 1 through 5 is _________________________.

In the previous section, we found Euler circuits using an algorithm that involved joining circuits together into one large circuit. You can also use Fleury’s algorithm to find Euler circuits in any graph with vertices of all even degree. In that case, you can start at any vertex that you would like to use.

Step 1: Begin at any vertex.

Step 2: Remove an edge between the vertex and any adjacent vertex that is NOT a bridge, unless there is no other choice, making a note of the edge you removed. Repeat this step until all edges are removed.

Step 3: Write out the Euler circuit using the sequence of vertices and edges that you found. For example, if you removed ab, bc, cd, de, and ea, in that order, then the Euler circuit is abcdea.

Checkpoint

IMPORTANT! Since a circuit is a closed trail, every Euler circuit is also an Euler trail, but when we say Euler trail in this chapter, we are referring to an open Euler trail that begins and ends at different vertices.

Example 12.32

Finding an Euler Circuit or Euler Trail Using Fleury’s Algorithm

Use Fleury’s algorithm to find either an Euler circuit or Euler trail in Graph G in Figure 12.167.

Graph G has three quadrilaterals. The vertices of the first quadrilateral are b, d, e, and c. The vertices of the second quadrilateral are i, h, j, and k. The vertices of the third quadrilateral are n, m, o, and p. Other edges connect c to d, d to i, i to j, j to n, and n to o. A curved edge connects c and o.
Figure 12.167 Graph G

Your Turn 12.32

1.
Find an Euler circuit or trail through the graph using Fleury’s algorithm.
Graph T has six vertices.The vertices are u, z, x, v, y, and w. The edges connect u x, x w, u w, w v, w y, u x, and z y.
Figure 12.175 Graph T

WORK IT OUT

We have discussed a lot of subtle concepts in this section. Let’s make sure we are all on the same page. Work with a partner to explain why each of the following facts about bridges are true. Support your explanations with definitions and graphs.

  1. When a bridge is removed from a graph, the number of components increases.
  2. A bridge is never part of a circuit.
  3. An edge that is part of a triangle is never a local bridge.

Check Your Understanding

Fill in the blank to make the statement true.
51.
An Euler trail is a trail that visits each ___________ exactly once.
52.
__________ algorithm is a procedure for finding an Euler trail or circuit.
53.
An Euler _____ always begins and ends at the same vertex, but an Euler _____ does not.
54.
When a bridge is removed from a graph, the number of ________ is increased by one.
55.
When a __________ is removed from a graph, the shortest path between its vertices will be greater than two.
56.
When using Fleury’s algorithm to find an Euler trail, never remove a _________ unless it is the only option.

Section 12.6 Exercises

Use the figure to answer the following exercises. Identify the graph(s) with the given characteristics, if any.
Four graphs. Graph T has six vertices: a, b, c, d, e, and f. The edges connect a c, c e, e d, d a, a e, e b, b f, and f e. Graph U has eight vertices labeled a to h. The edges connect c b, b d, d h, h e, e g, g c, b a, a e, e f, f b, and g d. Graph V has four vertices, a to d. The edges connect a c, c b, b d, d a, a b, and d c. Graph W has 14 vertices labeled a to n. The edges from a lead to b, c, d, e, f, g, and h. The edges from b lead to i, j, k, l, m, and n.
1.
Connected
2.
All vertices of even degree
3.
Exactly two vertices of odd degree
4.
Has an Euler trail
5.
Has an Euler circuit
6.
Has neither an Euler trail nor an Euler circuit
7.
ab is a bridge
8.
ef is a bridge
9.
ab is a local bridge
10.
ef is a local bridge
Use the figure to answer the following exercises. In each exercise, a graph and a sequence of vertices are given. Determine whether each sequence of vertices is an Euler trail, an Euler circuit, or neither for the graph. If it is neither, explain why.
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. The edges connect s t, t v, v w, w x, x u, w u, u s, and u t. Graph D has 10 vertices. The edges from t lead to x, r, s, u, and q. The edges from x lead to v, w, y, and z. The edges connect r s, u q, v w, and y z.
Figure 12.176
11.
Graph A, wxyzwutsvu
12.
Graph A, uvstuwzyxw
13.
Graph A, stuvuwzyxw
14.
Graph A, wxyzwvutsv
15.
Graph B, uvwxrutsyzu
16.
Graph B, vwxruzystu
17.
Graph C, stuvwxs
18.
Graph C, tuxwustvw
19.
Graph D, trstuvtxvwxyzx
20.
Graph D, xvwxyzxtrstuvt
Use the figure to answer the following exercises. For each graph, identify a bridge if one exists. If it does not, state so. If it does, identify any components that are created when the bridge is removed.
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. The edges connect s t, t v, v w, w x, x u, w u, u s, and u t. Graph D has 10 vertices. The edges from t lead to x, r, s, u, and q. The edges from x lead to v, w, y, and z. The edges connect r s, u q, v w, and y z.
21.
Graph A
22.
Graph B
23.
Graph C
24.
Graph D
Use the figuree to answer the following exercises. For each graph, identify a local bridge if one exists. If it does not, state so. If it does, find a shortest path between the vertices of the local bridge if the local bridge is removed.
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. The edges connect s t, t v, v w, w x, x u, w u, u s, and u t. Graph D has 10 vertices. The edges from t lead to x, r, s, u, and q. The edges from x lead to v, w, y, and z. The edges connect r s, u q, v w, and y z.
25.
Graph A
26.
Graph B
27.
Graph C
28.
Graph D
Use the graphs to answer the following exercises. In each exercise, a graph is given. Find two Euler trails in each graph using Fleury’s algorithm.
Three graphs. Graph Q has five vertices: c, d, e, f, and g. The edges connect c d, d e, e g, g f, f c, d f, and d g. Graph R has five vertices: h, i, j, k, and m. The edges connect h i, k, k m, m j, j h, and j k. Graph S has five vertices: n, o, p, q, and r. The edges connect n o, o q, q r, q p, r p, p o, and p n.
29.
Graph Q
30.
Graph R
31.
Graph S
32.
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.
An illustration shows a 5 by 5 square chess board. The 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 left or right.
A graph in which each vertex represents a space on a five-by-six game board and each edge represents a move a knight could make is shown in the figure.
An illustration shows a 5 by 6 chessboard. Each square has a vertex. It displays several edges representing all possible knight moves. An illustration shows vertices arranged in 5 rows and 6 columns. The edges represent the knight's moves.
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 closed knight’s tour in the figure is most accurately described as a trail, a circuit, an Euler trail, or an Euler circuit of the graph of all possible knight moves. Explain your reasoning.
A graph represents a knight's moves on a 5 by 6 chessboard. The knight is at the bottom-left square. The knight moves in an L-shape. The movement of the knight inside the 5 by 6 board is mapped and connected with edges.
33.
Determine if the open knight’s tour in the figure is most accurately described as a trail, a circuit, an Euler trail, or an Euler circuit of the graph of all possible knight moves on a five-by-five game board. Explain your reasoning.
A graph represents a knight's moves on a 5 by 5 chessboard. The knight is at the center square of the board. The knight moves in an L-shape. The movement of the knight inside the 5 by 5 board is mapped and connected with edges.
34.
The neighborhood of Pines West has three cul-de-sacs that meet at an intersection as shown in the figure. A postal delivery person starts at the intersection and visits each house in a cul-de-sac once, returns to the intersection, visits each house in the next cul-de-sac, and so on, returning to the intersection when finished. Describe how the route can be represented as a graph. If there is no backtracking, in other words, the person never reverses direction, is the route followed by the postal delivery person best described as a trail, a circuit, an Euler trail, or an Euler circuit? Explain your reasoning.
A map of Pines West. The map shows a start point at the center leading to three paths. Each path has six vertices. The start point is indicated by a vertex.
35.
Recall that the bridges of Konigsberg can be represented as a multigraph as shown in the figure. We have seen that no route through Konigsberg passes over each bridge exactly once and returns to the starting point. Is there a route that passes over each bridge exactly once but does not begin and end at the same point? Explain your reasoning.
A graph of Konigsberg Bridges has four vertices. The vertices are connected with edges forming two right cones.
36.
The figure shows the map of the exhibits at an indoor aquarium. Use a graph in which the edges represent hallways and the vertices represent turns and intersections to explain why a visitor to the aquarium cannot start at one of the turns or intersections, passes by every exhibit exactly once, and end at one of the turns or intersections.
A map of aquarium exhibits. The vertices are labeled A to S. The entrance is at the bottom.
37.
The map of the states of Imaginaria is given. Use a graph to determine if it is possible to begin in one state, travel through Imaginaria crossing the border between each pair of states exactly once, and end in a different state. If it is possible, find such a route. If it is not, explain why.
A map of Imaginaria. It has four regions: Fictionville, Illusionham, Mythbury, and Pretendstead.
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.