Discrete Mathematics:

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.

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

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?

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.

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.

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.

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.

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.