CM Euler Circuits and Kwan’s Mail Carrier Problem

Section 15.2 Euler Circuits and Kwan’s Mail Carrier Problem

In Example 15.1.4, 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 paths and Euler circuits.

An Euler path is a type of path that uses every edge in a graph with no repeats. Being a path, it does not have to return to the starting vertex.
An Euler circuit is a type of circuit that uses every edge in a graph with no repeats. Being a circuit, it must start and end at the same vertex.

Example 15.2.1.

In the graph shown below, there are several Euler paths. One such path is CABDCB. The path is shown in arrows to the right, with the order of edges numbered.

Example 15.2.3.

The graph below has several possible Euler circuits. Here are a couple, starting and ending at vertex A: ADEACEFCBA and AECABCFEDA. The second is shown in arrows.

Look back at Example 15.2.1, which showed a graph that had an Euler path. Does that graph have an Euler circuit? A few tries will tell you no; that graph does not have an Euler circuit.

Why do we care if an Euler circuit exists? Think back to Example 15.1.1 from the beginning of the chapter. 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.

Euler’s Path and Circuit Theorems.

A graph in which all vertices have even degree (that is, there are no odd vertices) will contain an Euler circuit.
A graph with exactly two vertices of odd degree will contain an Euler path, but not an Euler circuit.
A graph with any number of odd vertices other than zero or two will not have any Euler path.

Example 15.2.5.

In the graph below, vertices A and C have degree 4, since there are 4 edges leading into each vertex. B is degree 2, D is degree 3, and E is degree 1. This graph contains two vertices with odd degree (D and E) and three vertices with even degree (A, B, and C), so Euler’s theorems tell us this graph has an Euler path, but not an Euler circuit.

Example 15.2.6.

Is there an Euler circuit on the housing development lawn inspector graph we created in Example 15.1.1? All the highlighted vertices have odd degree. Since there are more than two vertices with odd degree, there are no Euler paths or Euler circuits on this graph. Unfortunately our lawn inspector will need to do some backtracking.

Example 15.2.7.

When it snows in the same housing development, the snowplow has to plow both sides of every street. For simplicity, we’ll assume the plow is out early enough that it can ignore traffic laws and drive down either side of the street in either direction. This can be visualized in the graph by drawing two edges for each street, representing the two sides of the street.

Notice that every vertex in this graph has even degree, so this graph does have an Euler circuit.

Now we know how to determine if a graph has an Euler circuit, but if it does, how do we find one? While it usually is 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.

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

Example 15.2.8.

Let’s find an Euler Circuit on this graph using Fleury’s algorithm, starting at vertex A.

Exploration 15.2.1.

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

Solution.

Yes, all vertices have even degree so this graph has an Euler circuit. There are several possibilities. One is: ABEGFCDFEDBCA

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. In order to do that, she will have to duplicate some edges in the graph until an Euler circuit exists.

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 degree. Connecting two odd degree vertices increases the degree of each, giving them both even degree. 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 there wasn’t one before. Duplicating edges would mean walking or driving down a road twice, while creating an edge where there wasn’t one before is akin to installing a new road!

Example 15.2.9.

For the rectangular graph shown, three possible eulerizations are shown. Notice in each of these cases the vertices that started with odd degrees have even degrees after eulerization, allowing for an Euler circuit.

In the example above, you’ll notice that the last Eulerization required duplicating seven edges, while the first two only required duplicating five edges. If we were Eulerizing the graph to find a walking path, we would want the Eulerization with minimal duplications. If the edges had weights representing distances or costs, then we would want to select the Eulerization with the minimal total added weight.

Exploration 15.2.2.

Eulerize the graph shown, then find an Euler circuit on the Eulerized graph.

Solution.

This graph can be Eulerized by duplicating the edge BC, as shown. One possible Euler circuit on the Eulerized graph is ACDBCBA

Example 15.2.11.

Looking again at the graph for our lawn inspector from Example 15.1.1 and Example 15.2.6, the vertices with odd degree are shown highlighted. With eight vertices, we will always have to duplicate at least four edges. In this case, we need to duplicate five edges since two odd degree vertices are not directly connected. Without weights we can’t be certain this is the Eulerization that minimizes walking distance, but it looks pretty good.

The problem of finding the optimal Eulerization is called the Kwan’s Mail Carrier Problem, a name given by an American in honor of the Chinese mathematician Meigu Guan

Also sometimes romanized as Mei-Ko Kwan.

who first studied the problem in 1962 while trying to find optimal delivery routes for postal carriers. This problem is important in determining efficient routes for garbage trucks, school buses, parking meter checkers, street sweepers, and more.

Unfortunately, algorithms to solve this problem are fairly complex. Some simpler cases are considered in the exercises.

Prev Top Next