5. [10] Alice and Bob play a game on a graph G, alternately choosing distinct vertices....

Transcribed Image Text:

5. [10] Alice and Bob play a game on a graph G, alternately choosing distinct vertices. Alice starts by choosing any vertex. Each subsequent choice must be adjacent to the preceding choice (of the other player). Thus together they follow a path. The last player able to move wins. Prove that Bob has a winning strategy if G has a perfect matching, and otherwise Alice has a winning strategy. 5. [10] Alice and Bob play a game on a graph G, alternately choosing distinct vertices. Alice starts by choosing any vertex. Each subsequent choice must be adjacent to the preceding choice (of the other player). Thus together they follow a path. The last player able to move wins. Prove that Bob has a winning strategy if G has a perfect matching, and otherwise Alice has a winning strategy.