13.2 Euler Paths and Euler Circuits 855 We are now ready to introduce Euler’s theorem, which is used to determine if a graph contains Euler paths and Euler circuits. As you will see, the number of odd vertices of a graph determines whether the graph has Euler paths and Euler circuits. Solution a) The graph in Fig. 13.20(a) has many Euler circuits, each of which is also an Euler path. One Euler circuit is ABDEBCEFCA , , , , , , , , , . Trace this circuit now. Notice that you traced each edge exactly one time and that you started and finished with vertex A. Notice that this graph has no odd vertices (and therefore has all even vertices). This graph has both Euler paths and Euler circuits. b) Using trial and error, we can see that the graph in Fig. 13.20(b) has an Euler path but it does not have an Euler circuit. One Euler path is C A B D C E F D , , , , , , , . Another Euler path is D B A C D F E C , , , , , , , . There are actually several Euler paths for this graph, but each one must begin at either vertex C or vertex D. If the Euler path begins at vertex C, it must end at vertex D, and vice versa (you should try to determine a few more to confirm this observation). Notice that there are exactly two odd vertices, vertex C and vertex D. c) Our attempts to trace the graph in Fig. 13.20(c) lead to either tracing at least one edge twice or to omitting at least one of the edges. We must therefore conclude that this graph has neither an Euler path nor an Euler circuit. Notice that this graph has more than two odd vertices. 7 Now try Exercise 7 Did You Know? Topology m DNA molecule Graph theory is part of a larger branch of mathematics known as topology . Although topology involves concepts from other older branches of mathematics, such as geometry, algebra, and analysis, topology was not recognized as a separate branch of mathematics until the 1920s and 1930s when the writings of Solomon Lefschetz (see Profile in Mathematics on page 880) established many of the fundamental aspects of the field of study. Topology is frequently referred to as rubbersheet geometry. This descriptive name refers to topology’s focus on geometric properties that remain consistent even when an object is bent, twisted, or stretched (see Section 8.6). One of the more interesting areas within topology is knot theory. Once a very obscure area of mathematics, knot theory is becoming increasingly important because of its applications to science. Among other things, knot theory is used to study DNA molecules, to discover new drugs, and to study how infectious diseases spread. Euler’s Theorem For a connected graph, the following statements are true. 1. A graph with no odd vertices (all even vertices) has at least one Euler circuit, which is also an Euler path. An Euler circuit can be started at any vertex, and it will end at the same vertex. 2. A graph with exactly two odd vertices has at least one Euler path but no Euler circuits. Each Euler path must begin at one of the two odd vertices, and it will end at the other odd vertex. 3. A graph with more than two odd vertices has neither an Euler path nor an Euler circuit. Example 2 Using Euler’s Theorem Use Euler’s theorem to determine whether an Euler path or an Euler circuit exists in Fig. 13.20(a), (b), and (c). Solution a) The graph in Fig. 13.20(a) has no odd vertices (all the vertices are even). According to item 1 in Euler’s theorem, at least one Euler circuit exists. An Euler circuit can be determined starting at any vertex. The Euler circuit will end at the vertex from which it started. Recall that each Euler circuit is also an Euler path. b) We see that the graph in Fig. 13.20(b) has four even vertices A B E F (, , ,and ) and two odd vertices C D ( and ). Based on item 2 in Euler’s theorem, we conclude that since there are exactly two odd vertices, at least one Euler path exists but no Euler circuit exists. Each Euler path must begin at one of the odd vertices and end at the other odd vertex. c) The graph in Fig. 13.20(c) has four odd vertices A B D E ( , , , and ) and one even vertex C( ). According to item 3 in Euler’s theorem, since this graph has more than two odd vertices, the graph has neither an Euler path nor an Euler circuit. 7 Now try Exercise 9 The proof of this theorem is beyond the scope of this book. In Example 2, we will reexamine the graphs used in Example 1. However, this time we will use Euler’s theorem to determine whether the graph has Euler paths and Euler circuits. Nobeastsofierce/Shutterstock
RkJQdWJsaXNoZXIy NjM5ODQ=