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 i1 from the left side of the graph, then player II naming an actress j1 that has starred with i1 from the right side, then player I naming an actor i2 from the left side that has starred with j1, and so on. No repetition of names is allowed. The player who cannot respond with a new name loses the game. Show that II has a winning strategy if the graph G has a perfect matching, and I has a winning strategy otherwise.

(4) Let G be an n x 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 ji that has starred with ij from the right side, then player I naming an actor iz from the left side that has starred with ji, and so on. No repetition of names is allowed. The player who cannot respond with a new name loses the game. Show that II has a winning strategy if the graph G has a perfect matching, and I has a winning strategy otherwise