# Proving a game has a winning strategy over a graph $G$ if and only if $G$ has no perfect matching

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.

• 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.) – Brian M. Scott Apr 26 '16 at 1:45
• Thank you, but showing that if there is winning strategy then G has a perfect mathcing is what I'm having trouble with. – Ben-ZT Apr 26 '16 at 14:17