12.5: Euler Circuits

Figure \(\PageIndex{1}\) : Delivery trucks move goods from place to place. (credit: “Mack Midliner” by Jason Lawrence/Flickr, CC BY 2.0)

Learning Objectives

1. Determine if a graph is connected.
2. State the Chinese postman problem.
3. Describe and identify Euler Circuits.
4. Apply the Euler Circuits Theorem.
5. 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 \(\PageIndex{2}\) 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 \(\PageIndex{2}\) : 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 \(\PageIndex{3}\) . 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 \(\PageIndex{3}\) : 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 \(\PageIndex{4}\) , it is easier to see that the graph is disconnected.

Figure \(\PageIndex{4}\) : Untangling Graph X

Versions 2 and 3 of Graph X in Figure \(\PageIndex{4}\) 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 \(\PageIndex{3}\) . 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 \(\PageIndex{5}\) : Untangling Graph Y

Example \(\PageIndex{1}\): Determining If a Graph Is Connected or Disconnected

Use Figure \(\PageIndex{6}\) to answer each question.

Figure \(\PageIndex{6}\) Graph E

1. Find a path between vertex a and every other vertex on the graph, if possible.
2. Identify all the components of Graph E.
3. Determine whether the graph is connected or disconnected and explain how you know.

Answer

1. The paths are a → d → b, a → d → c, and a → d.
2. There is only one component in Graph E. It has the vertices {a, b, c, d}.
3. 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 \(\PageIndex{1}\)

Determine whether each graph is connected or disconnected and identify the set of vertices that make up each of its components.

Figure \(\PageIndex{7}\)

Video

Connected and Disconnected Graphs in Graph Theory

Example \(\PageIndex{2}\): Applying Connectedness

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 \(\PageIndex{2}\)

“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 \(\PageIndex{8}\) . 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 \(\PageIndex{8}\) : 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 \(\PageIndex{9}\) . 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.

Video

Recognizing Euler Trails and Euler Circuits

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 \(\PageIndex{9}\) : 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 \(\PageIndex{10}\) .

Figure \(\PageIndex{10}\) : A Vertex of Degree 3

First imagine the vertex of degree 3 shown in Figure \(\PageIndex{10}\) 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 \(\PageIndex{10}\) 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 \(\PageIndex{11}\) to solve the Konigsberg Bridge Problem. Since the degrees of the vertices of the graph in Figure \(\PageIndex{10}\) 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 \(\PageIndex{11}\) : Degrees of Vertices in Konigsberg Bridge Multigraph

Video

Existence of Euler Circuits in Graph Theory

Chinese Postman Problem

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 \(\PageIndex{12}\) .

Figure \(\PageIndex{12}\) : 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 \(\PageIndex{13}\) .

Figure \(\PageIndex{13}\) : 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 \(\PageIndex{14}\) . 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 \(\PageIndex{14}\) : Degrees of Vertices in Graph of Canoe Event

Example \(\PageIndex{3}\): Understanding Eulerian Graphs

A postal delivery person must deliver mail to every block on every street in a local subdivision. Figure \(\PageIndex{15}\) is a map of the subdivision. Use the map to answer each question.

Figure \(\PageIndex{15}\) Map of Subdivision

1. Draw a graph or multigraph to represent the subdivision in which the vertices represent the intersections, and the edges represent streets.
2. Is your graph connected? Explain how you know.
3. Determine the degrees of the vertices in the graph.
4. Is your graph an Eulerian graph?
5. Is it possible for the postal delivery person to visit each block on each street exactly once? Justify your answer.

Answer

1. The graph is in Figure \(\PageIndex{16}\) .

   

   Figure \(\PageIndex{16}\) Graph of Subdivision

2. The graph is connected. It has only one component and there is a path between each pair of vertices.
3. 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.
4. The graph is not Eulerian because it has vertices of odd degree.
5. 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 \(\PageIndex{3}\)

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 \(\PageIndex{17}\): 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.

1. Is your graph connected? Explain how you know.
2. Determine the degrees of the vertices in the graph.
3. Is your graph an Eulerian graph?
4. 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 \(\PageIndex{18}\), 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 \(\PageIndex{18}\): 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 \(\PageIndex{19}\) shows one possible circuit that we could use as the first circuit, 1 → A → 2 → B → 3 → C → 4 → G → 5 → J → 1.

Figure \(\PageIndex{19}\): 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 \(\PageIndex{20}\).

Figure \(\PageIndex{20}\): 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

$$1\to A\to \boxed{2}\to B\to \boxed{3}\to C\to 4\to G\to 5\to J\to 1$$

becomes

$$\begin{array}{l}1\to A\to \boxed{2\to D\to 6\to E\to 7\to F\to 2}\to B\to \\ \boxed{3\to H\to 5\to I\to 1\to K\to 3}\to C\to 4\to G\to 5\to J\to 1\end{array}$$

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 \(\PageIndex{4}\): Finding an Euler Circuit

Use Figure \(\PageIndex{21}\) to answer each question.

Figure \(\PageIndex{21}\) Graph F

1. Verify the Graph F is Eulerian.
2. Find an Euler circuit that begins and ends at vertex c.

Answer

1. 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 \(\PageIndex{22}\). So, the graph is Eulerian.

   

   Figure \(\PageIndex{22}\) Degrees of Vertices in Graph F

2. Step 1: Beginning at vertex c, identify circuit c → e → b → c as shown in Figure \(\PageIndex{23}\). Since this circuit does not cover every edge in the graph, move on to Step 2.

   

   Figure \(\PageIndex{23}\): First Circuit in Graph F

   Step 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 \(\PageIndex{24}\), 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 \(\PageIndex{24}\): Second Circuit in Graph F

   Step 3: Combine the two circuits into one. Replace vertex b in the first circuit with the whole second circuit that begins at vertex b. $$\begin{array}{c}c\to e\to \boxed{b}\to \end{array}$$cbecomesc→e→b→d→c→a→b→cc→e→b→cbecomesc→e→b→d→c→a→b→c.
   An Euler circuit that begins at vertex c is c → e → b → d → c → a → b → c.

Your Turn \(\PageIndex{4}\)

Use Graphs X and Y to answer each question.

Figure \(\PageIndex{25}\)

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 \(\PageIndex{26}\) to create the graph in Figure \(\PageIndex{27}\).

Figure \(\PageIndex{26}\): Map of Subdivision

Figure \(\PageIndex{27}\): 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 \(\PageIndex{28}\), 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 \(\PageIndex{28}\): 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 \(\PageIndex{28}\), 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 \(\PageIndex{5}\): Eulerizing Graphs

Use Graph A and multigraphs B, C, D, and E given in Figure \(\PageIndex{29}\) to answer the questions.

Figure \(\PageIndex{29}\) Graph A and Multigraphs B through E

1. Which of the multigraphs are not eulerizations of Graph A? Explain your answer.
2. Which eulerization of Graph A uses the fewest duplicate edges? How many does it use?
3. 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

1. 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.
2. Multigraph C uses 3 duplicate edges while multigraph D only uses 2. So, D uses the fewest.
3. 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 \(\PageIndex{5}\)

Create an eulerization using the fewest duplicate edges possible for Graph Z.

Figure \(\PageIndex{30}\): 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 \(\PageIndex{31}\): 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:

1. 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?
2. 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.

Exercise \(\PageIndex{1}\)

A disconnected graph has only one component.

Exercise \(\PageIndex{2}\)

A graph that has all vertices of even degree is connected.

Exercise \(\PageIndex{3}\)

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.

Exercise \(\PageIndex{4}\)

A graph with vertices of all even degree is Eulerian.

Exercise \(\PageIndex{5}\)

An Eulerian graph has all vertices of even degree.

Exercise \(\PageIndex{6}\)

An Euler circuit is a closed trail.

Exercise \(\PageIndex{7}\)

An Euler circuit is a closed path

Exercise \(\PageIndex{8}\)

To eulerize a graph, add new edges between previously nonadjacent vertices until no vertices have odd degree.

Exercise \(\PageIndex{9}\)

To eulerize a graph, add duplicate edges between adjacent vertices until no vertices have odd degree.

Exercise \(\PageIndex{10}\)

The number of duplicate edges required to eulerize a graph is half the number of vertices of odd degree.