Figure 12.117: Delivery trucks move goods from place to place. (credit: “Mack Midliner” by Jason Lawrence/Flickr, CC BY 2.0)
Learning Objectives
Determine if a graph is connected.
State the Chinese postman problem.
Describe and identify Euler Circuits.
Apply the Euler Circuits Theorem.
Evaluate Euler Circuits in real-world applications.
The delivery of goods is a huge part of our daily lives. From the factory to the distribution center, to the local vendor, or to your front door, nearly every product that you buy has been shipped multiple times to get to you. If the cost and time of that delivery is too great, you will not be able to afford the product. Delivery personnel have to leave from one location, deliver the goods to various places, and then return to their original location and do all of this in an organized way without losing money. How do delivery services find the most efficient delivery route? The answer lies in graph theory.
Connectedness
Before we can talk about finding the best delivery route, we have to make sure there is a route at all. For example, suppose that you were tasked with visiting every airport on the graph in Figure 12.118 by plane. Could you accomplish that task, only taking direct flight paths between airports listed on this graph? In other words, are all the airports connected by paths? Or are some of the airports disconnected from the others?
Figure 12.118: Major Central and South Florida Airports
In Figure 12.118, we can see TPA is adjacent to PBI, FLL, MIA, and EYW. Also, there is a path between TPA and MCO through FLL. This indicates there is a path between each pair of vertices. So, it is possible to travel to each of these airports only taking direct flight paths and visiting no other airports. In other words, the graph is connected because there is a path joining every pair of vertices on the graph. Notice that if one vertex is connected to each of the others in a graph, then all the vertices are connected to each other. So, one way to determine if a graph is connected is to focus on a single vertex and determine if there is a path between that vertex and each of the others. If so, the graph is connected. If not, the graph is disconnected, which means at least one pair of vertices in a graph is not joined by a path. Let’s take a closer look at graph X in Figure 12.119. Focus on vertex a. There is a path between vertices a and b, but there is no path between vertex a and vertex c. So, Graph X is disconnected.
Figure 12.119: Connected vs. Disconnected
When you are working with a planar graph, you can also determine if a graph is connected by untangling it. If you draw it so that so that none of the edges are overlapping, like we did with Graph X in Figure 12.119, it is easier to see that the graph is disconnected.
Figure 12.120: Untangling Graph X
Versions 2 and 3 of Graph X in Figure 12.120 each have the same number of vertices, number of edges, degrees of the vertices, and pairs of adjacent vertices as version 1. In other words, each version retains the same structure as the original graph. Since versions 2 and 3 of Graph X, do not have overlapping edges, it is easier to identify pairs of vertices that do not have paths between them, and it is more obvious that Graph X is disconnected. In fact, there are two completely separate, disconnected subgraphs, one with the vertices in {a, b, e}, and the other with the vertices {c, d, f}
These sets of vertices together with all of their edges are called components of Graph X. A component of a graph is a subgraph in which there is a path between each pair of vertices in the subgraph, but no edges between any of the vertices in the subgraph and a vertex that is not in the subgraph.
Now let’s focus on Graph Y from Figure 12.119. As in Graph X, there is a path between vertices a and b, as well as between vertices a and e, but Graph Y is different from Graph X because of vertex g. Not only is there a path between vertices a and g, but vertex g bridges the gap between a and c with the path a → b → g → c. Similarly, there is a path between vertices a and d and vertices a and f: a → b → g → d, a → b → g → d → f. Since there is a path between vertex a and every other vertex, Graph Y is connected. You can also see this a bit more clearly by untangling Graph Y as in Figure 12.121. Even when Y is drawn so that the edges do not overlap, the graph cannot be drawn as two separate, unconnected pieces. In other words, Graph Y has only one component with the vertices {a, b, c, d, e, f}.
We can give an alternate definition of connected and disconnected using the idea of components. A graph is connected if it has only one component. A graph is disconnected if it has more than one component. These alternate definitions are equivalent to the previous definitions. This means that you can confirm a graph is connected or disconnected either by checking to see if there is a path between each vertex and each other vertex, or by identifying the number of components. A graph is connected if it has only one component.
Figure 12.121: Untangling Graph Y
Example 12.24: Determining If a Graph Is Connected or Disconnected
Use Figure 12.122 to answer each question.
Figure 12.122 Graph E
Find a path between vertex a and every other vertex on the graph, if possible.
Identify all the components of Graph E.
Determine whether the graph is connected or disconnected and explain how you know.
Answer
The paths are a → d → b, a → d → c, and a → d.
There is only one component in Graph E. It has the vertices {a, b, c, d}.
The graph is connected, because there is a path between vertex a and every other vertex. We can also so that Graph E is connected because it has only one component.
Your Turn 12.24
Determine whether each graph is connected or disconnected and identify the set of vertices that make up each of its components.
Figure 12.123
The U.S. Interstate Highway System extends throughout the 48 contiguous states. It also has routes in the states of Hawaii and Alaska, and the commonwealth of Puerto Rico. Consider a graph representing the U.S. Interstate Highway System, in which there is a vertex for each of the 50 states and Puerto Rico, and an edge is drawn between any two vertices representing states that are connected by a highway in that system. Would this graph be connected or disconnected? Explain your reasoning.
Answer
Hawaii, Alaska, and Puerto Rico are geographically separate from the 48 contiguous states, and each from each other. This means that there are vertices on the graph with no path joining them to the other vertices. So the graph is disconnected.
Your Turn 12.25
“Six degrees of separation” is the idea that any two people on Earth are connected by at most six social connections. Assume that this is true. Consider a graph in which each vertex is a person on Earth, and each edge is a social connection. Would this graph be connected or disconnected? Explain your reasoning.
Origin of Euler Circuits
The city of Konigsberg, modern day Kaliningrad, Russia, has waterways that divide up the city. In the 1700s, the city had seven bridges over the various waterways. The map of those bridges is shown in Figure 12.124. The question as to whether it was possible to find a route that crossed each bridge exactly once and return to the starting point was known as the Konigsberg Bridge Problem. In 1735, one of the most influential mathematicians of all time, Leonard Euler, solved the problem using an area of mathematics that he created himself, graph theory!
Figure 12.124: Map of the Bridges of Konigsberg in 1700s (credit: “Konigsberg Bridge” by Merian Erben/Wikimedia Commons, Public Domain)
Euler drew a multigraph in which each vertex represented a land mass, and each edge represented a bridge connecting them, as shown in Figure 12.125. Remember from Navigating Graphs that a circuit is a trail, so it never repeats an edge, and it is closed, so it begins and ends at the same vertex. Euler pointed out that the Konigsberg Bridge Problem was the same as asking this graph theory question: Is it possible to find a circuit that crosses every edge? Since then, circuits (or closed trails) that visit every edge in a graph exactly once have come to be known as Euler circuits in honor of Leonard Euler.
Euler was able to prove that, in order to have an Euler circuit, the degrees of all the vertices of a graph have to be even. He also proved that any graph with that characteristic must have an Euler circuit. So, saying that a connected graph is Eulerian is the same as saying it has vertices with all even degrees, known as the Eulerian circuit theorem.
Figure 12.125: Graph of Konigsberg Bridges
To understand why the Euler circuit theorem is true, think about a vertex of degree 3 on any graph, as shown in Figure 12.126.
Figure 12.126: A Vertex of Degree 3
First imagine the vertex of degree 3 shown in Figure 12.126 is not the starting vertex. At some point, each edge must be traveled. The first time one of the three edges is traveled, the direction will be toward the vertex, and the second time it will be away from the vertex. Then, at some point, the third edge must be traveled coming in toward the vertex again. This is a problem, because the only way to get back to the starting vertex is to then visit one of the three edges a second time. So, this vertex cannot be part of an Euler circuit.
Next imagine the vertex of degree 3 shown in Figure 12.126 is the starting vertex. The first time one of the edges is traveled, the direction is away from the vertex. At some point, the second edge will be traveled coming in toward the vertex, and the third edge will be the way back out, but the starting vertex is also the ending vertex in a circuit. The only way to return to the vertex is now to travel one of the edges a second time. So, again, this vertex cannot be part of an Euler circuit.
For the same reason that a vertex of degree 3 can never be part of an Euler circuit, a vertex of any odd degree cannot either. We can use this fact and the graph in Figure 12.127 to solve the Konigsberg Bridge Problem. Since the degrees of the vertices of the graph in Figure 12.126 are not even, the graph is not Eulerian and it cannot have an Euler circuit. This means it is not possible to travel through the city of Konigsberg, crossing every bridge exactly once, and returning to your starting position.
Figure 12.127: Degrees of Vertices in Konigsberg Bridge Multigraph
At Camp Woebegone, campers travel the waterways in canoes. As part of the Camp Woebegone Olympics, you will hold a canoeing race. You have placed a checkpoint on each of the 11 different streams. The competition requires each team to travel each stream, pass through the checkpoints in any order, and return to the starting line, as shown in the Figure 12.128.
Figure 12.128: Map of Canoe Event Checkpoints
Since the teams want to go as fast as possible, they would like to find the shortest route through the course that visits each checkpoint and returns to the starting line. If possible, they would also like to avoid backtracking. Let’s visualize the course as a multigraph in which the vertices represent turns and the edges represent checkpoints as in Figure 12.129.
Figure 12.129: Multigraph of Canoe Event
The teams would like to find a closed walk that repeats as few edges as possible while still visiting every edge. If they never repeat an edge, then they have found a closed trail, which is a circuit. That circuit must cover all edges; so, it would be an Euler circuit. The task of finding a shortest circuit that visits every edge of a connected graph is often referred to as the Chinese postman problem. The name Chinese postman problem was coined in honor of the Chinese mathematician named Kwan Mei-Ko in 1960 who first studied the problem.
If a graph has an Euler circuit, that will always be the best solution to a Chinese postman problem. Let’s determine if the multigraph of the course has an Euler circuit by looking at the degrees of the vertices in Figure 12.130. Since the degrees of the vertices are all even, and the graph is connected, the graph is Eulerian. It is possible for a team to complete the canoe course in such a way that they pass through each checkpoint exactly once and return to the starting line.
Figure 12.130: Degrees of Vertices in Graph of Canoe Event
Example 12.26: Understanding Eulerian Graphs
A postal delivery person must deliver mail to every block on every street in a local subdivision. Figure 12.131 is a map of the subdivision. Use the map to answer each question.
Figure 12.131 Map of Subdivision
Draw a graph or multigraph to represent the subdivision in which the vertices represent the intersections, and the edges represent streets.
Is your graph connected? Explain how you know.
Determine the degrees of the vertices in the graph.
Is your graph an Eulerian graph?
Is it possible for the postal delivery person to visit each block on each street exactly once? Justify your answer.
Answer
The graph is in Figure 12.132.
Figure 12.132 Graph of Subdivision
The graph is connected. It has only one component and there is a path between each pair of vertices.
There are four corner vertices of degree 2, there are eight exterior vertices of degree 3, and there are four interior vertices of degree 4.
The graph is not Eulerian because it has vertices of odd degree.
No. Since the graph is not Eulerian, there is no Euler circuit, which means that there is no route that would pass through every edge exactly once.
Your Turn 12.26
A pest control service has at least one customer on every block of every street or cul-de-sac in a neighborhood. Use the map of the neighborhood to answer each question.
Figure 12.133: Map of Neighborhood
Draw a graph or multigraph of the neighborhood in which the vertices represent intersections, and the edges represent the streets between them.
Is your graph connected? Explain how you know.
Determine the degrees of the vertices in the graph.
Is your graph an Eulerian graph?
Is it possible for the postal delivery person to visit each block on each street exactly once and start and end at the same position? Justify your answer.
Identifying Euler Circuits
Solving the Chinese postman problem requires finding a shortest circuit through any graph or multigraph that visits every edge. In the case of Eulerian graphs, this means finding an Euler circuit. The method we will use is to find any circuit in the graph, then find a second circuit starting at a vertex from the first circuit that uses only edges that were not in the first circuit, then find a third circuit starting at a vertex from either of the first two circuits that uses only edges that were not in the first two circuits, and then continue this process until all edges have been used. In the end, you will be able to link all the circuits together into one large Euler circuit.
Let’s find an Euler circuit in the map of the Camp Woebegone canoe race. In Figure 12.134, we have labeled the edges of the multigraph so that the circuits can be named. In a multigraph it is necessary to name circuits using edges and vertices because there can be more than one edge between adjacent vertices.
Figure 12.134: Multigraph of Canoe Race with Vertices and Edges Labeled
We will begin with vertex 1 because it represents the starting line in this application. In general, you can start at any vertex you want. Find any circuit beginning and ending with vertex 1. Remember, a circuit is a trail, so it doesn’t pass through any edge more than once. Figure 12.135 shows one possible circuit that we could use as the first circuit, 1 → A → 2 → B → 3 → C → 4 → G → 5 → J → 1.
Figure 12.135: First Circuit
From the edges that remain, we can form two more circuits that each start at one of the vertices along the first circuit. Starting at vertex 3 we can use 3 → H → 5 → I → 1 → K → 3 and starting at vertex 2 we can use 2 → D → 6 → E → 7 → F → 2, as shown in Figure 12.136.
Figure 12.136: Second and Third Circuits
Now that each of the edges is included in one and only once circuit, we can create one large circuit by inserting the second and third circuits into the first. We will insert them at their starting vertices 2 and 3
becomes
Finally, we can name the circuit using vertices, 1 → 2 → 6 → 7 → 2 → 3 → 5 → 1 → 3 → 4 → 5 → 1, or edges, A → D → E → F → B → H → I → K → C → G → J.
Let's review the steps we used to find this Eulerian Circuit.
Steps to Find an Euler Circuit in an Eulerian Graph
Step 1 - Find a circuit beginning and ending at any point on the graph. If the circuit crosses every edges of the graph, the circuit you found is an Euler circuit. If not, move on to step 2.
Step 2 - Beginning at a vertex on a circuit you already found, find a circuit that only includes edges that have not previously been crossed. If every edge has been crossed by one of the circuits you have found, move on to Step 3. Otherwise, repeat Step 2.
Step 3 - Now that you have found circuits that cover all of the edges in the graph, combine them into an Euler circuit. You can do this by inserting any of the circuits into another circuit with a common vertex repeatedly until there is one long circuit.
Example 12.27: Finding an Euler Circuit
Use Figure 12.137 to answer each question.
Figure 12.137 Graph F
Verify the Graph F is Eulerian.
Find an Euler circuit that begins and ends at vertex c.
Answer
The graph is connected because it has only one component. Also, each of the vertices in graph F has even degree as shown in Figure 12.138. So, the graph is Eulerian.
Figure 12.138 Degrees of Vertices in Graph F
Step 1: Beginning at vertex c, identify circuit c → e → b → c as shown in Figure 12.139. Since this circuit does not cover every edge in the graph, move on to Step 2.
Figure 12.139: First Circuit in Graph FStep 2: Find another circuit beginning at one of the vertices in the first circuit, using only edges that have not been used in the first circuit. It is possible to do this using either vertex c or vertex b. In Figure 12.140, we have used vertex b as the starting and ending point for a second circuit, b → d → c → a → b. Since all edges have been crossed by one of the two circuits, move on to Step 3.
Figure 12.140: Second Circuit in Graph FStep 3: Combine the two circuits into one. Replace vertex b in the first circuit with the whole second circuit that begins at vertex b. .
An Euler circuit that begins at vertex c is c → e → b → d → c → a → b → c.
Your Turn 12.27
Use Graphs X and Y to answer each question.
Figure 12.141
Which graph does not have an Euler circuit? Explain how you know.
Find an Euler circuit in the other graph.
Eulerization
The Chinese postman problem doesn’t only apply to Eulerian graphs. Recall the postal delivery person who needed to deliver mail to every block of every street in a subdivision. We used the map in Figure 12.142 to create the graph in Figure 12.143.
Figure 12.142: Map of SubdivisionFigure 12.143: Graph of Subdivision
Since the graph of the subdivision has vertices of odd degree, there is no Euler circuit. This means that there is no route through the subdivision that visits every block of every street without repeating a block. What should our delivery person do? They need to repeat as few blocks as possible. The technique we will use to find a closed walk that repeats as few edges as possible is called eulerization. This method adds duplicate edges to a graph to create vertices of even degree so that the graph will have an Euler circuit.
In Figure 12.144, the eight vertices of odd degree in the graph of the subdivision are circled in green. We have added duplicate edges between the pairs of vertices, which changes the degrees of the vertices to even degrees so the resulting multigraph has an Euler circuit. In other words, we have eulerized the graph.
Figure 12.144: An Eulerized Graph
The duplicate edges in the eulerized graph correspond to blocks that our delivery person would have to travel twice. By keeping these duplicate edges to a minimum, we ensure the shortest possible route. It can be challenging to determine the fewest duplicate edges needed to eulerize a graph, but you can never do better than half the number of odd vertices. In the graph in Figure 12.144, we have found a way to fix the eight vertices of odd degree with only four duplicate edges. Since four is half of eight, we will never do better.
Checkpoint
IMPORTANT! The duplicate edges that we add indicate places where the route will pass twice. An entirely new edge between two vertices that were not previously adjacent would indicate that our postal delivery person created a new road through someone’s property! So, we can duplicate existing edges, but we cannot create new ones.
Example 12.28: Eulerizing Graphs
Use Graph A and multigraphs B, C, D, and E given in Figure 12.145 to answer the questions.
Figure 12.145 Graph A and Multigraphs B through E
Which of the multigraphs are not eulerizations of Graph A? Explain your answer.
Which eulerization of Graph A uses the fewest duplicate edges? How many does it use?
Is it possible to eulerize Graph A using fewer duplicate edges than your answer to part 2? If so, give an example. If not, explain why not.
Answer
Multigraph B is not an eulerization of A because the edge N between vertices c and d is not a duplicate of an existing edge. Multigraph E is not an eulerization of A because vertices b and e have odd degree.
Multigraph C uses 3 duplicate edges while multigraph D only uses 2. So, D uses the fewest.
Since there were four vertices in Graph A, the fewest number of edges that could possibly eulerize the graph is half of four, which is two. So, it is not possible to eulerize Graph A using fewer edges.
Your Turn 12.28
Create an eulerization using the fewest duplicate edges possible for Graph Z.
Figure 12.146: Graph Z
Checkpoint
IMPORTANT! Since only duplicate edges can be added to eulerize a graph, it is not possible to eulerize a disconnected graph.
WORK IT OUT
Figure 12.147: Map of the Magical Land of Oz (credit: “Map of Oz within the surrounding deserts” by L. Frank Baum/Wikimedia Commons, Public Domain)
In The Wonderful Wizard of Oz, written by L. Frank Baum and illustrated by W. W. Denslow, the region of 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. Draw a graph in which each vertex is one of the regions of Oz. Then answer each question:
Is there an Euler trail circuit 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 and back, passing over each border exactly once? If not, how could the graph be Eulerized most efficiently?
What is the chromatic number of the graph? Find a graph coloring that demonstrates your answer and use it to draw and color a graph of Oz.
Check Your Understanding
For the following exercises, determine whether each statement is always true, sometimes true, or never true.
41.
A disconnected graph has only one component.
42.
A graph that has all vertices of even degree is connected.
43.
There is a route through the city of Konigsberg that a person may pass over each bridge exactly once and return to the starting point.
44.
A graph with vertices of all even degree is Eulerian.
45.
An Eulerian graph has all vertices of even degree.
46.
An Euler circuit is a closed trail.
47.
An Euler circuit is a closed path
48.
To eulerize a graph, add new edges between previously nonadjacent vertices until no vertices have odd degree.
49.
To eulerize a graph, add duplicate edges between adjacent vertices until no vertices have odd degree.
50.
The number of duplicate edges required to eulerize a graph is half the number of vertices of odd degree.
Section 12.5 Exercises
Use Graphs A, B, C, D, E, F, G, H, and I to answer the following exercises. Identify any graph or graphs with the given characteristics or indicate that none do.
Figure 12.148
1.
Connected
2.
Disconnected
3.
Exactly two components
4.
Exactly three components
5.
Exactly four components
6.
Exactly five components
7.
At least one vertex of odd degree
8.
All vertices of even degree
9.
An Euler circuit
10.
A path between vertex j and each other vertex on the same graph
Use the graphs in the previous exercise to answer the following exercises. For each exercise, list the set of vertices for each component in the given graph.
11.
Graph B
12.
Graph E
13.
Graph F
14.
Multigraph I
Use the graphs in the initial exercise to answer the following exercises. For each exercise, a graph and a vertex on the graph are given. Find a path between the given vertex and each other vertex on the graph. If this is not possible, indicate that it is not.
15.
Graph A, vertex c.
16.
Graph B, vertex m.
17.
Graph D, vertex x.
18.
Graph F, vertex w.
19.
Graph G, vertex a.
20.
Graph H, vertex e.
Use the graphs in the initial exercise to answer the following exercises. For each exercise, a graph and a vertex on the graph are given. Find an Euler circuit beginning and ending at the given vertex if one exists. If no Euler circuits exist, explain how you know that they do not.
21.
Graph A, vertex c.
22.
Graph B, vertex k.
23.
Graph D, vertex w.
24.
Graph G, vertex b.
25.
Graph H, vertex o.
26.
Multigraph I, vertex p.
For the following exercises, use the connected graphs. In each exercise, a graph is indicated. Determine if the graph is Eulerian or not and explain how you know. If it is Eulerian, give an example of an Euler circuit. If it is not, state which edge or edges you would duplicate to eulerize the graph.
27.
Graph J
28.
Graph K
29.
Multigraph L
30.
Graph M
31.
The figure shows a map of zoo exhibits A through P with walkways shown in gray. Draw a graph, or multigraph, to represent the routes through the zoo in which the edges represent walkways and the vertices represent turns and intersections, which are each marked with a star. Notice that there is exactly one exhibit between each pair of adjacent vertices. Label the edges with the corresponding exhibit. Use it to determine if it is possible for a visitor to begin at the entrance, view each exhibit exactly once, and end back at the entrance. If it is possible, give an example of a circuit on the graph that would represent a route the visitor could take. If it is not possible, explain why.
The figure shows the map of the exhibits at an indoor aquarium with hallways shown in gray. Turns and intersections of hallways are marked with stars.
32.
Use the Euler circuit theorem and 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 the entrance, visit every exhibit exactly once, and return to the entrance.
33.
Use an eulerization of the graph you found to determine the least amount of backtracking necessary to allow a visitor to begin at the entrance, see every exhibit at least once, and return to the entrance. How many hallways must be covered twice? Explain your reasoning.
The map of the states of Imaginaria is given.
34.
Use a graph to determine if it is possible to travel through Imaginaria crossing each the border between each pair of states exactly once, and returning to the state in which you started.
35.
Use an eulerization of the graph you found to determine the fewest borders that must be covered twice in order to cross each border at least once and return to the state in which you started. Explain your reasoning.
