850 CHAPTER 13 Graph Theory 7. The number of edges that connect to a vertex is called the _______ of the vertex. Degree 8. A bridge is an edge that, if removed from a connected graph, would create a(n) _______ graph. Disconnected Practice the Skills In Exercises 9–14, create a graph with the given properties. There are many possible answers for each problem. 9. Two even and two odd vertices * 10. Four odd vertices * 11. Seven vertices and one bridge * 12. Eight vertices and one bridge * 13. Three even vertices and one loop * 14. Four odd vertices and one loop * In Exercises 15–20, use the following graph to answer the following questions. A B C D E 15. a) Is A C B E D , , , , a path? Explain. No, there is no edge connecting vertices B and E. b) Is D E C B A , , , , a path? Explain. Yes, there are edges connecting vertex D to vertex E, vertex E to vertex C, vertex C to vertex B, and vertex B to vertex A. c) Is D E C B A , , , , a circuit Explain. No, the path does not begin and end with the same vertex. d) Is D E C A B D , , , , , a circuit? Explain. Yes, it is a path that begins and ends with the same vertex. 16. a) Is A B C D E , , , , a path? Explain. No, there is no edge connecting vertices C and D. b) Is A B C E D , , , , a path? Explain. Yes, there are edges connecting vertex A to vertex B, vertex B to vertex C, vertex C to vertex E, and vertex E to vertex D. c) Is A B C E D , , , , a circuit? Explain. No, the path does not begin and end with the same vertex. d) Is A B D E C A , , , , , a circuit? Explain. Yes, it is a path that begins and ends with the same vertex. 17. a) On the graph, is it possible to determine a path that begins with vertex B, contains all the edges exactly once, and ends with vertex C? If so, determine one such path. Yes. One example is B A C E D B C , , , , , , . b) On the graph, is it possible to determine a path that begins with vertex A, contains all the edges exactly once, and ends with vertex B? If so, determine one such path. No c) On the graph, it possible to determine a circuit that begins and ends with vertex A and includes all the edges exactly one time? If so, determine one such circuit. No 18. a) On the graph, is it possible to determine a path that begins with vertex C, contains all the edges exactly once, and ends with vertex B? If so, determine one such path. Yes. One example is C A B D E C B , , , , , , . b) On the graph, is it possible to determine a path that begins with vertex D, contains all the edges exactly once, and ends with vertex E? If so, determine one such path. No c) On the graph, is it possible to determine a circuit that begins and ends with vertex E and includes all the edges exactly one time? If so, determine one such circuit. No 19. On the graph, is it possible to determine a circuit that begins and ends with vertex B and contains all the other vertices exactly once? If so, determine one such circuit. Yes. One example is B A C E D B , , , , , . 20. On the graph, is it possible to determine a circuit that begins and ends with vertex C and contains all the other vertices exactly once? If so, determine one such circuit. Yes. One example is C E D B A C , , , , , . In Exercises 21–24, determine whether the graph shown is connected or disconnected. 21. B F G D C A E Disconnected 22. B F E A C D Connected 23. A E D C G B F Connected 24. A F G D I B H J K E Disconnected *See Instructor Answer Appendix
RkJQdWJsaXNoZXIy NjM5ODQ=