Two people play a game over a graph $G$ choosing alternately different vertices $v_1,v_2,...$ such that, for every $i>0$, $v_i$ is adjacent to $v_{i-1}$. The last player capable of choosing a vertex is the winner. Proof that the player who chooses the first player has a winning strategy if and only if $G$ doesn´t have a perfect matching.

I know that the sufficiency proof is trivial, but I'm having trouble with the necessity proof. I thought maybe induction would be useful, but I can't seem to use it appropriately. Any ideas would be helpful. Thanks.

  • $\begingroup$ You’ve shown that the first player can win if $G$ has no perfect matching? For the other direction show that if $G$ does have a perfect matching, the second player can win. (I think that it’s actually easiest to show that $G$ has a perfect matching iff the second player can win.) $\endgroup$ – Brian M. Scott Apr 26 '16 at 1:45
  • $\begingroup$ Thank you, but showing that if there is winning strategy then G has a perfect mathcing is what I'm having trouble with. $\endgroup$ – Ben-ZT Apr 26 '16 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.