856 CHAPTER 13 Graph Theory The results determined in Example 2 using Euler’s theorem are the same as the results determined in Example 1 using trial and error. Although both methods led to the same result, Euler’s theorem is superior to trial and error because it gives us a tool to examine more complicated graphs. Next, we will use Euler’s theorem to solve questions regarding the Königsberg bridge problem as well as problems relating to the graphs we developed in Section 13.1. Example 3 Solving the Königsberg Bridge Problem In Section 13.1, Example 1, we discussed the Königsberg bridge problem and drew a graph to represent the situation. The graph is repeated in Fig. 13.21. Could a walk be taken through Königsberg during which each bridge is crossed exactly one time? Solution The vertices of the graph given in Fig. 13.21 represent the land areas, and the edges of the graph represent the bridges in the Königsberg bridge problem. The original problem posed by the townspeople of Königsberg, in graph theory terms, was whether or not an Euler path exists for the graph in Fig. 13.21. From the figure, we see that the graph has four odd vertices A B C D ( , , , and ). Thus, according to item 3 of Euler’s theorem, no Euler path exists. Therefore, no walk could be taken through Königsberg in which each bridge was crossed exactly one time. 7 Now try Exercise 21 A D B C Figure 13.21 Example 4 Vacationing in the Southwest In Section 13.1, Example 2, we discussed the Jugo family, who are vacationing in the Southwestern portion of the United States. We drew a graph showing the states they plan to visit that share a common border. The graph is repeated in Fig. 13.22. CA NV NM CO AZ UT Figure 13.22 a) Is it possible for the Jugo Family to travel among these six states and cross each common state border (or use each edge) exactly one time? b) If yes, determine a path that the Jugo Family could take to travel between these states and cross each common state border exactly one time. Solution a) Since the Jugo Family must use each edge (or common border) exactly one time, they are seeking an Euler path for the graph in Fig. 13.22. Notice that this graph has exactly two odd vertices, NV and UT. According to item 2 of Euler’s theorem, at least one Euler path, but no Euler circuit, exists. Therefore, it is possible for them to travel among these states and cross each common state border exactly one time. However, since there is no Euler circuit, they must start their travel and end their travel in different states. b) Many Euler paths exist, but each one must either start with NV and end with UT or start with UT and end with NV. One such path is NV UT CO NM AZ , , , , , CA NV AZ UT , , , . There are many other Euler paths on this graph. You should try to determine at least two now. 7 Now try Exercise 25 m Carlsbad Caverns, New Mexico Galyna Andrushko/ Shutterstock
RkJQdWJsaXNoZXIy NjM5ODQ=