7.2: Euler Circuits and Eulerization of Graph

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. Describe and identify Euler paths and Circuits.
2. Apply the Euler Circuit Theorem.
3. State the Chinese postman problem.
4. 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.

Origin of Euler Circuits and Terminology of Euler Path and Circuit

The city of Konigsberg, modern day Kaliningrad, Russia, has waterways that divide up the city. In the \(1700\)s, the city had seven bridges over the various waterways. The map of those bridges is shown in Figure \(\PageIndex{2}.\) 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 he created himself: graph theory!

Figure \(\PageIndex{2}:\) Map of the Bridges of Konigsberg in \(1700\)s (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{3}.\) 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.

Figure \(\PageIndex{3}\): Graph of Map of the Bridges of Konigsberg

In the first section, we created a graph of the Königsberg bridges and asked whether it was possible to walk across every bridge once. Because Euler first studied this question, these types of paths are named after him.

Euler Trail and Euler Circuit

Euler Trails starts and ends at two (distinct) vertices and traverses every edge exactly once.

Euler Circuit: Starts and ends at the same vertex and traverses every edge exactly once.
Note: In previous section we know trail is not necessarily path, but in this section. We will use Euler trail as Euler path. 

Eulerian Graph

The graph is called Eulerian if it contains an Eulerian circuit.

Semi‐Eulerian if it contains an Eulerian trail but not an Eulerian circuit.

Euler paths and Euler circuits are useful in many real-life situations where you need to travel through connections efficiently without repeating edges (roads, links, wires, routes, etc.). Here’s a clear and simple explanation of where they are used:

Euler’s Path and Circuit Theorem

	Condition	Where to Start and End
Euler Circuit	All vertices are even	We can start at any even vertex and must end at the same vertex
Euler Path or Euler Trail (No Euler Circuit)	Exactly two odd vertices	We must start from one odd vertex and end at another odd vertex
No Euler Path and Euler Circuit	More than 2 odd vertices

Your Turn \( \PageIndex{1 \): Euler Theorem

Euler Path and Euler Circuit

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

Example \(\PageIndex{2}\): Find a Euler Path

In the graph shown below, there are several Euler paths. Find one such path. What is the degree of the vertex that you start and end at to find such a path?

Figure \(\PageIndex{4}\)

 

Answer

One such path is CABDCB. The path is shown in arrows to the right, with the order of edges numbered.

Figure \(\PageIndex{5}\)

You can write the above path in different ways

\(C, A, B, D, C, B\)

OR

\(C \rightarrow A \rightarrow B \rightarrow D \rightarrow C \rightarrow B \)

The degree of the vertex that we start is \(3\) (C: odd degree), and the degree of the vertex that we end is \(3\) (B: odd degree).

Your Turn \( \PageIndex{2} \): Euler Path

 

Example \(\PageIndex{3}\): Find a Euler Path

Does the graph below have an Euler Circuit? If so, find one.

Figure \(\PageIndex{6}\)

Answer

All vertices have even degrees, so this graph has an Euler Circuit (By Euler’s Path and Circuit Theorem). There are several possibilities. One is ABEGFCDFEDBCA. We can write the same circuit another way, as follows

\(A \rightarrow B \rightarrow E \rightarrow G\rightarrow F \rightarrow C \rightarrow D \rightarrow F \rightarrow E \rightarrow D \rightarrow B \rightarrow C \rightarrow A\)

Since this graph has an Euler Circuit, we call this graph an Eulerian graph.

Your Turn \( \PageIndex{3} \): Euler Circuit

 

Your Turn \( \PageIndex{4} \): Euler Path, Euler Circuit or Neither?

Here is a portion of a housing development. As part of her job, the development’s lawn inspector has to walk down every street to ensure the homeowners’ landscaping conforms to the community requirements.

Naturally, she wants to minimize the amount of walking she has to do. Is it possible for her to walk down every street in this development without doing any backtracking? While you might be able to answer that question just by looking at the picture for a while, it would be ideal to be able to answer the question for any picture regardless of its complexity job; the development’s lawn inspector has to walk down every street in the development, making sure homeowners’ landscaping conforms to the community requirements.

Figure \(\PageIndex{7}\): Portion of Housing Development

Why care if an Euler circuit exists? The lawn inspector is interested in walking as little as possible. The ideal situation would be a circuit that covers every street with no repeats. That’s an Euler circuit! Luckily, Euler solved the question of whether or not an Euler path or circuit will exist.

Is there an Euler circuit on the housing development map Figure Figure \(\PageIndex{7},\) which is represented by the following graph in Figure \(\PageIndex{8}.\) All the highlighted vertices have odd degrees (Figure \(\PageIndex{9}.\)) Since there are more than two vertices with odd degrees, this graph has no Euler paths or circuits. Unfortunately, our lawn inspector will need to do some backtracking.

Figure \(\PageIndex{8}\)

Figure \(\PageIndex{9}\)

Now we know how to determine if a graph has an Euler circuit, but how do we find one if it does? While it is usually possible to find an Euler circuit just by pulling out your pencil and trying to find one, the more formal method is Fleury’s algorithm.

Fleury’s Algorithm: To Find the Euler Path and Euler Circuit

1. Start at any vertex if finding an Euler circuit. If finding an Euler path, start at one of the two vertices with odd degree.
2. Choose any edge leaving your current vertex, provided that deleting that edge will not separate the graph into two disconnected sets of edges.
3. Add that edge to your circuit and delete it from the graph.
4. Continue until you’re done.

Example \(\PageIndex{5}\): Finding an Euler Circuit

Using Fleury's algorithm, starting at vertex A, let’s find an Euler Circuit on this graph.

Figure \(\PageIndex{10}\)

Answer

All vertices are even, so it has an Euler Circuit. In other words, it is an Eulerian graph.

Choose an edge AD.

Figure \(\PageIndex{10}\)

Delete AD: See Figure \(\PageIndex{11}. We can’t choose DC since that would disconnect the graph.

Figure \(\PageIndex{11}\)

Choose DE. Delete DE. See figure \(\PageIndex{12}.\) From E, there is only one option, so the rest of the circuit is determined.

Figure \(\PageIndex{12}\)

Circuit: ADEBDCA

or

\(A\rightarrow D \rightarrow E \rightarrow B \rightarrow D \rightarrow C \rightarrow A \)

Your Turn \( \PageIndex{5} \): Find Euler Circuit

Example \(\PageIndex{6}\): Finding an Euler Path using Fleury’s Algorithm

Use Fleury’s Algorithm to find an Euler trail for Graph J in Figure \(\PageIndex{13}.\)

Figure \(\PageIndex{13}\): Graph J

Answer

Choose one of the two vertices of odd degree, c or f, as your starting vertex, since you must start from one odd vertex.

Figure \(\PageIndex{14}\): Graph J with cb Removed

The next choice is to remove edge ba, bd, or bf, as shown in Figure \(\PageIndex{14},\) but bf is not an option since it is a bridge. As shown in Figure \(\PageIndex{15},\) we will choose ba as the second edge removed.

Figure \(\PageIndex{15}\): raph J with cb and ba Removed

For the third, fourth, fifth, sixth, and seventh edges. As shown in Figure \(\PageIndex{15},\) until we get to the seventh edge, there is only one option each time: ac, cd, db, and bf in that order. For the seventh edge, we must choose between fe and fg. Neither of these is a bridge. We choose fe. Figure \(\PageIndex{16}\) shows that ac, cd, db, bf, and fe have been removed.

Figure \(\PageIndex{16}\): Graph J with Seven Edges Removed

Write out the Euler trail using the vertices in the sequence in which the edges were removed. We removed cb, ba, ac, cd, db, bf, fe, eh, hi, ig, and gf, in that order. The Euler trail is

c → b → a → c → d → b → f → e → h → i → g → f

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

Your Turn \( \PageIndex{6} \): Find Euler Circuit

Chinese Postman Problem

Imagine you're a postman and must deliver mail by walking along every street in a neighborhood at least once, then return to your starting point. Naturally, you want to walk the shortest possible distance. How can you find the shortest closed path that covers every edge in a graph at least once? The name Chinese postman problem was coined in honor of the Chinese mathematician named Kwan Mei-Ko in \(1960,\) who first studied the problem. This problem is essential in determining efficient routes for garbage trucks, school buses, parking meter checkers, and street sweepers.

Definition: Chinese Postman Problem

The task of finding the shortest circuit that visits every edge of a connected graph is often referred to as the Chinese Postman problem. In a given graph , the task is to find the shortest closed path that visits every edge at least once. The postman can traverse edges more than once if necessary, but each edge must be traversed at least once.

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

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

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

Draw a graph or multigraph to represent the subdivision in which the vertices represent the intersections and the edges represent the streets.

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? Justify your answer.

Answer

 

Figure \(\PageIndex{18}\): Graph of Subdivision

The graph is show in Figure \(\PageIndex{18}.\)

1. The graph is connected. It has only one component and a path between each pair of vertices.
2. There are four corner vertices of degree \(2,\) eight exterior vertices of degree \(3,\) and four interior vertices of degree \(3.\)
3. The graph is not Eulerian because it has vertices of odd degrees.
4. No. Since the graph is not Eulerian, there is no Euler circuit, meaning there is no route that would pass through every edge exactly once.

Your Turn \(\PageIndex{7}\)

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{19\): 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. Can the postal delivery person visit each block on each street exactly once and start and end at the same position? Justify your answer.

Non-Eulerian Graph (Chinese Postman Problem)

Not every graph has an Euler path or circuit, yet our lawn inspector still needs to do her inspections. Her goal is to minimize the amount of walking she has to do. To do that, she will have to duplicate some edges in the graph until an Euler circuit exists. The problem of finding the optimal Eulerization is called the Chinese Postman Problem.

Eulerization

Eulerization is the process of adding edges to a graph to create an Euler circuit on a graph. To eulerize a graph, edges are duplicated to connect pairs of vertices with odd degrees. Connecting two odd-degree vertices increases the degree of each, giving them both even degrees. When two odd-degree vertices are not directly connected, we can duplicate all edges in a path connecting the two.

Note that we can only duplicate edges, not create edges where none existed. Duplicating edges would mean walking or driving down a road twice while creating an edge where there wasn’t one before, which is akin to installing a new road!

Figure \(\PageIndex{20}\): Non Eulerian Graph

Three possible eulerizations for graph in figure \(\PageIndex{25}\) are shown in figure \(\PageIndex{26}\). Notice that in each of these cases, the vertices that started with odd degrees have even degrees after Eulerization, allowing for an Euler circuit.

Figure \(\PageIndex{21}\): Three Possible Eulerization

In the example above, you’ll notice that the last Eulerization in figure \(\PageIndex{21}\) required duplicating seven edges, while the first two only required duplicating five. If we were Eulerizing the graph to find a walking path, we would want the Eulerization with minimal duplications.

Example \(\PageIndex{8}\): Eulerized Map of Subdivision

Eulerized the graph of the Map of Subdivision given in figure \(\PageIndex{17}.\)

Figure \(\PageIndex{18}\): Graph of Subdivision

Answer

In Figure \(\PageIndex{22},\) the eight vertices of odd degrees 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 shown below in figure \(\PageIndex{22}.\)

Figure \(\PageIndex{22}\): An Eulerized Graph

Your Turn \( \PageIndex{8}\): Eulerization of Graph

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.

Checkpoint

For the following problem, the goal is achievable if this graph has an Euler path.

Your Turn \( \PageIndex{9} \): Understand Euler Path

Check Your Understanding

1. For the following exercises, determine whether each statement is always true, sometimes true, or never true.
2. 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.
3. A graph with vertices of all even degrees is Eulerian.
4. An Eulerian graph has all vertices of even degree.
5. An Euler circuit is a closed trail.
6. An Euler circuit is a closed path.
7. To eulerize a graph, add new edges between previously nonadjacent vertices until no vertices have an odd degree.
8. To eulerize a graph, add duplicate edges between adjacent vertices until no vertices have an odd degree.
9. The number of duplicate edges required to pulverize a graph is half the number of vertices of odd degrees.