Answer Happy

Let G be an n×n bipartite graph, where vertices on one side correspond to actors, vertices on the other side correspond to actresses, and there is an edge between actor i and actress j if they have starred in a movie together. Consider a game where the players alternate naming names, with player I naming an actor i from the left side of the graph, then player II naming an actress j that has starred with i from the right side, then player I naming an actor i′ from the left side that has starred with j, and so on. No repetition of names is allowed. The player who cannot respond with a new name loses the game. For an example, see Figure 3.17. Show that II has a winning strategy if the graph G has a perfect matching, and I has a winning strategy otherwise. Hint: Player I's winning strategy in the latter case is to find a maximum matching in the graph, and then begin by naming an actor that is not in that maximum matching. FIGURE 3.17. In this game, if player I names Johnny Depp, then player II must name either Angelina Jolie or Penelope Cruz. In the latter case, player I must then name Tom Cruise, and player II must name Nicole Kidman. At this point, player I cannot name a new actor and loses the game.