Contemporary Mathematics

# 12.6Euler Trails

Contemporary Mathematics12.6 Euler Trails

Figure 12.131 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.132 to determine if each series of vertices represents a trail, an Euler trail, both, or neither. Explain your reasoning.

Figure 12.132 Graph H
1. abegfcde
3. gdabedcfge

Use the figure to determine if each sequence of vertices represents an Euler trail or not. If not, explain why.
Graph I
1.
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.132, 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.133. 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.

Figure 12.133 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.134. Could you find a route through the house that passes through each doorway exactly once?

Figure 12.134 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.135.

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

Figure 12.136 Degrees of Vertices in Five Rooms Puzzle

Since there are more than two vertices of odd degree as shown in Figure 12.136, 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.137, 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.

Figure 12.137 Graph with Bridges

Edges bf, cg, and dg are “bridges”

The graph in Figure 12.137 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.138. If we remove all three, the resulting graph in Figure 12.138 has four components.

Figure 12.138 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.139, 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.

Figure 12.139 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 may 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.140 to answer each question.

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

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.

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.142 shows the steps to find an Euler trail in a graph using Fleury’s algorithm.

Figure 12.142 Using Fleury’s Algorithm To Find Euler Trail

The Euler trail that was found in Figure 12.142 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.143.

Figure 12.143 Graph J

## Checkpoint

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

Use Graph L to fill in the blanks to complete the steps in Fleury’s algorithm.
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 ___.
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.147.

Figure 12.147 Graph G

1.
Find an Euler circuit or trail through the graph using Fleury’s algorithm.
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.

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

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.

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