2. Game of Slither. The game of Slither is played on a graph G = (V,E)...

Transcribed Image Text:

2. Game of Slither. The game of Slither is played on a graph G = (V,E) between two players. The players, called First and Second, play alternately, with First playing first. At each step 1 the player whose turn it is chooses a previously unchosen edge. The only rule is that at every step the set of chosen edges forms a simple path (i.e., a path with no repeated vertices). The loser is the first player unable to make a legal play at his or her turn. (i) q (ii) Show that if G has a perfect matching (a matching which leaves no vertex exposed), then First has a winning strategy. Suppose First's first move is an edge uv such that u is an inessential vertex of G. Show that Second can now force a win. [Recall that a vertex is inessential if there exist a maximum matching that leaves this vertex exposed] 2. Game of Slither. The game of Slither is played on a graph G = (V,E) between two players. The players, called First and Second, play alternately, with First playing first. At each step 1 the player whose turn it is chooses a previously unchosen edge. The only rule is that at every step the set of chosen edges forms a simple path (i.e., a path with no repeated vertices). The loser is the first player unable to make a legal play at his or her turn. (i) q (ii) Show that if G has a perfect matching (a matching which leaves no vertex exposed), then First has a winning strategy. Suppose First's first move is an edge uv such that u is an inessential vertex of G. Show that Second can now force a win. [Recall that a vertex is inessential if there exist a maximum matching that leaves this vertex exposed]