## Chapter5Euler Paths and Circuits

We begin this chapter with a practical problem. You are offered a job delivering mail in the neighborhood shown below to the left where the lines represent the streets of the neighborhood. The rules are simple:

1. You must deliver mail on each block, so must walk each block.

2. You may start and end anywhere because a friend drops you off and picks you up.

You first note that there are 41 blocks in the neighborhood. Your boss suggests that you use the route he used before he passed it on to you. That route is shown below to the right and consists of 53 blocks. The arrows represent the direction he walked each block and the solid circles represent the intersections.

Use the patterns below to find at least one path with fewer blocks than the one your boss suggests. Write out the best path you find in Problem 5.1.

###### Problem5.1.

Write down your best solution to the Mail Carrier Problem, labeling where you start and end, and numbering the blocks as you go.

1. How many blocks are in the neighborhood?

2. How many blocks must you walk in your best solution?

Clearly it is difficult to determine the shortest path, so let's examine some mini-neighborhoods illustrated on the next page.

###### Problem5.2.

For each graph on the next page write down:

1. the total number of blocks (edges) in the neighborhood, and

2. the smallest number of blocks that you can walk to deliver mail along each block, showing your path.

The mathematics behind the mail carrier problem dates to eighteenth century east Prussia. The historic city of Königsberg (now Kaliningrad) is broken into four regions by the forking Pregel River. Seven bridges connect the parts of the city as shown in Figure 5.4. Strolling the city, the residents of Königsberg found a challenge. Is there a path that would take them over each bridge exactly once?

###### Problem5.3.

Find a path connecting all four regions of Königsberg Figure 5.4 that takes you over each bridge exactly once.

Suppose we make each region of Königsberg a dot and each bridge a curved line connecting the respective regions. The result is shown in Figure 5.5. Now this problem looks like the mail carrier problem, except that we want to traverse each block exactly once.

The mathematical model Figure 5.5 of the Königsberg Bridge Problem in Figure 5.4 is called a graph and was invented (discovered?) by Leonard Euler, an eighteenth century resident of Königsberg, in order to solve the Königsberg Bridge Problem.

To solve the mail carrier problem and the Königsberg Bridge Problem, we will first try to decide when it is possible to find a path going over each block or each bridge exactly once. These problems may be rephrased mathematically in the language of graphs and Euler paths. Our goal is to determine when a given graph has an Euler path.

###### Definition5.6.

A graph consists of a finite set of points, called its vertices, and a finite set of line segments connecting them, called its edges.

Mathematicians do allow for graphs with an infinite number of vertices or edges, but for our class, we will restrict ourselves to the study of graphs with a finite number of vertices and edges.

###### Definition5.7.

A loop is an edge connecting a vertex to itself. Two or more edges between the same two vertices are called multiple edges.

###### Definition5.8.

A graph is connected if every pair of vertices is connected by some path. A graph is disconnected if it is not connected.

###### Problem5.9.

Can you draw a connected graph which has six vertices, four loops and two multiple edges? If so, do so. If not, why not?

###### Definition5.10.

The degree of a vertex in a graph is the number of edges coming into it. $($A loop counts as two edges.$)$ A vertex is even if its degree is an even number, and it is odd if its degree is an odd number.

###### Problem5.11.

Can you draw a connected graph with five vertices, each of degree four, which has no loops or multiple edges? If so, do so. If not, why not?

###### Problem5.12.

Can you draw a connected graph with three vertices of degree two and two vertices of degree three? If so, do so. If not, why not?

###### Problem5.13.

Can you draw a connected graph with two vertices of degree two and three vertices of degree three? If so, do so. If not, why not?

###### Problem5.14.

Can you draw a connected graph with one vertex of degree one, two vertices of degree two, three vertices of degree three and four vertices of degree four? If so, do so. If not, why not?

###### Definition5.15.

Two vertices are adjacent if an edge connects them.

###### Definition5.16.

A path is a sequence of adjacent vertices.

###### Definition5.17.

A circuit is a path of at least two vertices which starts and ends at the same vertex without repeating an edge.

###### Definition5.18.

An Euler path is a path that passes over every edge of the graph exactly once.

###### Definition5.19.

An Euler circuit is a circuit that passes over every edge of the entire graph.

###### Problem5.20.

Can you draw a connected graph with eight vertices and six edges which contains no circuit at all? If so, do so. If not, why not?

###### Problem5.21.

Can you draw a connected graph with exactly three edges that does not have an Euler path? If so, do so. If not, why not?

The next theorems tell us which graphs have an Euler path or an Euler circuit and how, if there is one, to find it.

From these two observations we can establish the following necessary conditions for a graph to have an Euler path or an Euler circuit.

The two theorems above tell us which graphs do not have an Euler path or circuit. We would like to know that all remaining graphs (connected graphs with either zero or two odd vertices) do have Euler paths. To do so requires a few theorems. Try to prove the next three problems, but don't let them slow you down. We can assume them and move on to the rest of the chapter and show them later when you get them.

###### Problem5.26.

Show that the sum of an odd number of odd numbers is odd.

###### Problem5.27.

Show that the sum of the degrees of the vertices of a graph is even.

###### Problem5.28.

Show that every graph has an even number of odd vertices.

###### Definition5.29.

An edge of a connected graph is called a cut edge if removal of that edge causes the graph to become disconnected.

Fleury's Algorithm.

1. Make a copy of the graph in pencil.

2. Start at one of the odd vertices if there are any; otherwise start at any vertex.

3. Follow a path in the copy, erasing each edge after you traverse it and numbering the corresponding edge in the original graph. The only rule is to traverse a cut edge only if you are at a degree one vertex of the remaining graph. If you are, then erase that vertex, traverse the cut edge, and then erase the cut edge.

4. Stop when there is no edge you can traverse.

See the Project section for a proof of Fleury's Theorem. There we will show that, when we apply Step 4, we will have an Euler Path.

###### Example5.31.

Illustrate Fleury's Algorithm in class using the graph in Figure 5.32. Applying Fleury's Algorithm and Fleury's Theorem will illustrate the next two Theorems.

###### Problem5.35.

Decide whether or not each of the three graphs in Figure 5.36 has an Euler path or an Euler circuit. If it has an Euler path or Euler circuit, trace it on the graph by marking the start and end, and numbering the edges. If it does not, then write a complete sentence explaining how you know it does not.

###### Problem5.37.

Use Fleury's Algorithm to find an Euler path in Figure 5.38.

Returning to our mail carrier problem, consider the problem of delivering mail in the top neighborhood illustrated in Figure 5.39. Because it has six odd vertices, we know that the graph has no Euler path and thus we can't find an Euler Circuit. Therefore, we can't travel down each block exactly once. What is the smallest number of blocks that we can walk and still deliver all the mail? To answer this we apply a process called the Eulerization of the graph. In the bottom copy of the graph in Figure 5.39, we have inserted four new edges so that the resulting graph has exactly two odd vertices. This is the minimum number of edges that will reduce the number of odd vertices to two. Because we can't build new roads (we are mail carriers, not city planners), the added edges represent the streets we must walk over twice, not new streets. The new graph is connected with exactly two odd vertices, so has an Euler Path of length $25 (original \ edges) + 4 (added \ edges) = 29 (total \ edges)$ blocks. This is the shortest possible path that will cover each block in the neighborhood.

###### Problem5.40.

Apply the Eulerization process to the original Mail Carrier Problem in Problem 5.1 at the beginning of the chapter. What is the minimum number of blocks that must be walked in order to deliver all the mail?

###### Problem5.41.

You are transferred to a new neighborhood, shown below. Apply the Eulerization process to this new neighborhood so that you add the minimum possible number of edges.

###### Problem5.42.

Using the dots below, copy your Eulerized graph above lightly with a pencil. Use Fleury's algorithm to find an Euler path for this graph. Be sure to mark the start and the end.