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 3 2 Terminology Every branch of mathematics has its own peculiar jargon and graph theory has more than its share In this section we will introduce some important concepts and terminology that we will need in the next three chapters Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 3 3 Example 5 10 Adjacency We say that two vertices in a graph are adjacent if they are joined by an edge In the graph shown in Fig 5 10 vertices A and B are adjacent and so are vertices B and C Vertices C and D are not adjacent and neither are vertices A and E Because of the loop EE we say that vertex E is adjacent to itself Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 3 4 Example 5 10 Adjacency We can also speak of edges being adjacent Two edges are said to be adjacent if they share a common vertex In the graph shown in Fig 5 10 AB and BF are adjacent edges and so are AB and AD On the other hand AB and DE are not adjacent Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 3 5 Example 5 11 Degree of a Vertex The degree of a vertex is the number of edges meeting at that vertex A loop counts twice toward the degree We will use the notation deg V to denote the degree of vertex V In Fig 5 10 the degrees of the vertices are as follows deg A 3 deg B 5 deg C 3 deg D 2 deg E 4 deg F 3 deg G 1 and deg H 1 Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 3 6 Example 5 11 Degree of a Vertex Because distinguishing vertices with an even degree from vertices with an odd degree is going to be critical later on we will often refer to vertices as even vertices or odd vertices depending on their degree The graph in Fig 5 10 has two even vertices D and E and six odd vertices all the others Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 3 7 Example 5 12 Paths and Circuits Paths and circuits both describe trips along the edges of a graph The only real difference between a path and a circuit is that a circuit is a closed trip the trip ends back at the starting point whereas a path is an open trip the starting and ending points are different In this context by a trip be it a path or a circuit we mean a sequence of adjacent edges with the property that an edge can be traveled just once Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 3 8 Example 5 12 Paths and Circuits The standard way to describe a path or a circuit is by listing the vertices in order of travel Here are a few examples of paths and circuits using the graph in Fig 5 10 A B E D is a path from vertex A to vertex D The edges of this path in order of travel are AB BE and ED The length of the path i e the number of edges in the path is 3 Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 3 9 Example 5 12 Paths and Circuits A B C A D E is a path of length 5 from A to E This path visits vertex A twice that s fine but no edge is repeated A B C B E is another path from A to E This path is only possible because there are two edges connecting B and C Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 3 10 Example 5 12 Paths and Circuits A C B E E D is a path of length 5 from A to D One of the edges in this path is the loop EE A B C B A D is not a path because the edge AB is traveled twice Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 3 11 Example 5 12 Paths and Circuits A B C B E E D A C B is not a path because the edge BC is traveled three times The first two passes are fine since there are two edges connecting B and C but a third pass requires that we travel through one of those edges a second time Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 3 12 Example 5 12 Paths and Circuits B C B is a circuit of length 2 Circuits of length 2 are possible when there are multiple edges The EE loop is considered to be a circuit of length 1 Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 3 13 Example 5 13 Connectedness and Bridges A graph is connected if you can get from any vertex to any other vertex along a path Essentially this means that the graph is all in one piece The graph shown in Fig 5 11 a is a connected graph Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 3 14 Example 5 13 Connectedness and Bridges Whereas the graphs shown in Fig 5 11 b and c are disconnected graphs Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 3 15 Example 5 13 Connectedness and Bridges A disconnected graph is made up of separate connected components Figure 5 11 b shows a disconnected graph with two components Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 3 16 Example 5 13 Connectedness and Bridges and Fig 5 11 c shows a disconnected graph with three components an isolated vertex is a component in and of itself Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 3 17 Example 5 13 Connectedness and Bridges Notice that Fig 5 11 b is the graph we get when we remove the edge BF from the graph in Fig 5 11 a Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 3 18 Example 5 13 Connectedness and Bridges This illustrates how the removal of just one edge from a connected graph can sometimes make the graph disconnected An edge whose removal makes a connected graph disconnected is called a bridge Thus we say that BF is a bridge in the graph in Fig 5 11 a The graph has two other bridges FG and FH Copyright 2010 Pearson Education Inc Excursions in Modern Mathematics 7e 5 3 19 Example 5 14 Euler Paths and Euler Circuits An Euler path in a connected graph is a path that travels through all …