5 The Mathematics of Getting Around 5 1 Euler Circuit Problems 5 2 What Is a Graph 5 3 Graph Concepts and Terminology 5 4 Graph Models 5 5 Euler s Theorems 5 6 Fleury s Algorithm 5 7 Eulerizing Graphs Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 5 2 Euler s Theroems In this section we are going to develop the basic theory that will allow us to determine if a graph has an Euler circuit an Euler path or neither This is important because as we saw in the previous section what are Euler circuit or Euler path questions in theory are real life routing questions in practice The three theorems we are going to see next all thanks to Euler are surprisingly simple and yet tremendously useful Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 5 3 EULER S CIRCUIT THEOREM If a graph is connected and every vertex is even then it has an Euler circuit at least one usually more If a graph has any odd vertices then it does not have an Euler circuit Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 5 4 How to Use the Theorem Here is how we can use Euler s circuit theorem First we make sure the graph is connected If it isn t then no matter what else an Euler circuit is impossible If the graph is connected then we start checking the degrees of the vertices one by one As soon as we hit an odd vertex we know that an Euler circuit is out of the question If there are no odd vertices then we know that the answer is yes the graph does have an Euler circuit Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 5 5 Illustration using the Theorem Figure 5 15 illustrates the three possible scenarios The graph in Fig 5 15 a cannot have an Euler circuit for the simple reason that it is disconnected Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 5 6 Illustration using the Theorem The graph in Fig 5 15 b is connected but we can quickly spot odd vertices C is one of them there are others This graph has no Euler circuits Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 5 7 Illustration using the Theorem But the graph in Fig 5 15 c is connected and all the vertices are even This graph does have Euler circuits Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 5 8 Summary of the Theorem The basic idea behind Euler s circuit theorem is that as we travel along an Euler circuit every time we go through a vertex we use up two different edges at that vertex one to come in and one to go out We can keep doing this as long as the vertices are even A single odd vertex means that at some point we are going to come into it and not be able to get out Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 5 9 EULER S PATH THEOREM If a graph is connected and has exactly two odd vertices then it has an Euler path at least one usually more Any such path must start at one of the odd vertices and end at the other one If a graph has more than two odd vertices then it cannot have an Euler path Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 5 10 Example 5 18 The Seven Bridges of K nigsberg Part 3 Back to the K nigsberg bridges problem In Example 5 15 we saw that the layout of the bridges in the old city can be modeled by the graph in Fig 5 16 a This graph has four odd vertices thus neither an Euler circuit nor an Euler path can exist Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 5 11 Example 5 18 The Seven Bridges of K nigsberg Part 3 We now have an unequivocal answer to the puzzle There is no possible way anyone can walk across all the bridges without having to recross some of them How many bridges will need to be recrossed It depends If we want to start and end in the same place we must recross at least two of the bridges Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 5 12 Example 5 18 The Seven Bridges of K nigsberg Part 3 One of the many possible routes is shown in Fig 5 16 b In this route the bridge connecting L and D is crossed twice and so is one of the two bridges connecting A and R Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 5 13 Example 5 18 The Seven Bridges of K nigsberg Part 3 If we are allowed to start and end in different places we can do it by recrossing just one of the bridges One possible route starting at A crossing bridge LD twice and ending at R is shown in Fig 5 16 c Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 5 14 Example 5 19 Child s Play Part 2 The graph in Fig 5 17 a is connected and the vertices are all even By Euler s circuit theorem we know that the graph has an Euler circuit which implies that the original line drawing has a closed unicursal tracing Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 5 15 Example 5 19 Child s Play Part 2 The graph in Fig 5 17 b is connected and has exactly two odd vertices C and D By Euler s path theorem the graph has an Euler path open unicursal tracing Moreover we now know that the path has to start at C and end at D or vice versa Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 5 16 Example 5 19 Child s Play Part 2 The graph in Fig 5 17 c has four odd vertices A B C and D so it has neither an Euler path nor an Euler circuit Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 5 17 Example 5 19 Child s Play Part 2 The full power of Euler s theorems is best appreciated when the graphs get bigger The graph in Fig 5 17 d is not extremely big but we can no longer eyeball an Euler circuit or path Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 5 18 Example 5 19 Child s Play Part 2 On the other hand a quick check of the degrees of the vertices shows that K and I are odd vertices and all the rest are even We are now in business an open unicursal tracing is possible as long as we start it at K or I and end it at the other one Starting anyplace else will lead to a dead …