Your friend Sue has a graph with eight vertices, labeled Vertex A, Vertex B, Vertex C,...

Transcribed Image Text:

Your friend Sue has a graph with eight vertices, labeled Vertex A, Vertex B, Vertex C, Vertex D, Vertex E, Vertex X, Vertex Y, and Vertex Z. The graph has nine edges, which are: АВ, АЕ, ВС, СD, CX, CZ, DE, XY, Y Z. Sue has arranged these nine edges into two mini-cycles: Mini-cycle 1: AB, BC, CD, DE, EA; Mini-cycle 2: XY, Y Z, ZC, CX. Can you help Sue put together her mini-cycles to get a full Euler cycle for the graph? Make sure to record the Euler cycle, and explain how you arrived at it. • Part B (3 pts): Cycle City consists of four islands, labeled A, B, C, and D. There are various bridges to help the residents get from island to island. The map is pictured below. The circles represent the islands, and the lines between circles (some curved, some straight) represent the bridges between islands. A B D The mayor of Cycle City, Bob the Bicyclist, would like to find a way to start at Island A, then bike around the island, using every bridge exactly once, so that he ends up back on Island A. Unfortunately, this is not possible. Explain why (you can freely use any theorems stated in class). • Part C (3pts): Bob the Bicyclist would like to add some bridges to Cycle City (pictured in Part B) so that he can start at Island A, bike around, using every bridge exactly once, and end up at A again. How many new bridges must he build? For full credit, explain why your answer is optimal (i.e., why you couldn't get away with fewer new bridges). Your friend Sue has a graph with eight vertices, labeled Vertex A, Vertex B, Vertex C, Vertex D, Vertex E, Vertex X, Vertex Y, and Vertex Z. The graph has nine edges, which are: АВ, АЕ, ВС, СD, CX, CZ, DE, XY, Y Z. Sue has arranged these nine edges into two mini-cycles: Mini-cycle 1: AB, BC, CD, DE, EA; Mini-cycle 2: XY, Y Z, ZC, CX. Can you help Sue put together her mini-cycles to get a full Euler cycle for the graph? Make sure to record the Euler cycle, and explain how you arrived at it. • Part B (3 pts): Cycle City consists of four islands, labeled A, B, C, and D. There are various bridges to help the residents get from island to island. The map is pictured below. The circles represent the islands, and the lines between circles (some curved, some straight) represent the bridges between islands. A B D The mayor of Cycle City, Bob the Bicyclist, would like to find a way to start at Island A, then bike around the island, using every bridge exactly once, so that he ends up back on Island A. Unfortunately, this is not possible. Explain why (you can freely use any theorems stated in class). • Part C (3pts): Bob the Bicyclist would like to add some bridges to Cycle City (pictured in Part B) so that he can start at Island A, bike around, using every bridge exactly once, and end up at A again. How many new bridges must he build? For full credit, explain why your answer is optimal (i.e., why you couldn't get away with fewer new bridges).