13.2 Euler Paths and Euler Circuits 861 Exercises Warm Up Exercises In Exercises 1– 6, fill in the blanks with an appropriate word, phrase, or symbol(s). 1. A path that passes through each edge of a graph exactly one time is called a(n) _________ path. Euler 2. A circuit that passes through each edge of a graph exactly one time is called a(n) _________ circuit. Euler 3. A connected graph has at least one Euler path that is also an Euler circuit, if the graph has _________ odd vertices. No 4. A connected graph has at least one Euler path, but no Euler circuits, if the graph has exactly _________ odd vertices. Two 5. A connected graph has neither an Euler path nor an Euler circuit, if the graph has more than two _________ vertices. Odd 6. If a connected graph has exactly two odd vertices, A and B, then each Euler path must begin at vertex A and end at vertex _________, or begin at vertex B and end at vertex A. B Practice the Skills For Exercises 7–10, use the following graph. A B D E C 7. a) Is it possible to determine an Euler path that begins with vertex A? If so, determine one such Euler path. Yes. One example is A B D E C A D C , , , , , , , . b) Is it possible to determine an Euler path that begins with vertex B? If so, determine one such Euler path. No. This graph has exactly two odd vertices, A and C. Each Euler path must begin at vertex A and end at vertex C or vice versa. 8. a) Is it possible to determine an Euler path that begins with vertex C? If so, determine one such Euler path. Yes. One example is C E D B A C D A , , , , , , , . b) Is It possible to determine an Euler path that begins with vertex D? If so, determine one such Euler path. No. This graph has exactly two odd vertices, A and C. Each Euler path must begin at vertex A and end at vertex C or vice versa. 9. Is it possible to determine an Euler circuit that begins with vertex E? If so, determine one such Euler circuit. No. A graph with exactly two odd vertices has no Euler circuits. 10. Is it possible to determine an Euler circuit for this graph? If so, determine one such Euler circuit. No. A graph with exactly two odd vertices has no Euler circuits. For Exercises 11–14, use the following graph. A B D F E C 11. Is it possible to determine an Euler path that begins with vertex A? If so, determine one such Euler path. No. A graph with more than two odd vertices has neither an Euler path nor an Euler circuit. 12. Is it possible to determine an Euler path that begins with ver tex B? If so, determine one such Euler circuit. No. A graph with more than two odd vertices has neither an Euler path nor an Euler circuit. 13. Is it possible to determine an Euler circuit that begins with ver tex C? If so, determine one such Euler circuit. No. A graph with more than two odd vertices has neither an Euler path nor an Euler circuit. 14. Is it possible to determine an Euler path that begins with vertex D? If so, determine one such Euler path. No. A graph with more than two odd vertices has neither an Euler path nor an Euler circuit. For Exercises 15–20, use the following graph. For each exercise, there are many possible answers. E D C F A B 15. Determine an Euler circuit that begins and ends with vertex A. ABCDEFBDFA , , , , , , , , , 16. Determine an Euler circuit that begins and ends with vertex B. BCDEFABDFB , , , , , , , , , 17. Determine an Euler circuit that begins and ends with vertex C. CDEFABDFBC , , , , , , , , , 18. Determine an Euler circuit that begins and ends with vertex D. DEFABCDFBD , , , , , , , , , 19. Determine an Euler circuit that begins and ends with vertex E. EFABCDFBDE , , , , , , , , , 20. Determine an Euler circuit that begins and ends with vertex F. FABFDBCDEF , , , , , , , , , Problem Solving Revisiting the Königsberg Bridge Problem In Exercises 21 and 22, suppose that the people of Königsberg decide to add several bridges to their city. Following are two such possibilities. a) Would the townspeople be able to walk across all the bridges without crossing the same bridge twice? b) If so, where should they begin and where would they end? SECTION 13.2
RkJQdWJsaXNoZXIy NjM5ODQ=