Two people play a game over a finite graph $G$ choosing alternately previously unchosen vertices $v_1,v_2,v_3,\ldots$ such that, for every integer $i>1$, the vertex $v_i$ is adjacent to $v_{i-1}$. The last player capable of choosing a vertex is the winner. Prove that the player who goes first has a winning strategy if and only if $G$ doesn't have a perfect matching.
I know that the necessity proof is trivial, but I'm having trouble with the sufficiency proof. I thought maybe induction would be useful, but I can't seem to use it appropriately. Any ideas would be helpful. Thanks.
Proof of the Forward Direction $(\Rightarrow)$.
Suppose that $G$ has a perfect matching $M$. Then, the second player always wins by picking a vertex $v$ such that $\{u,v\}\in M$, where $u$ is the vertex the first player has just played. Therefore, the first player does not have a winning strategy. By contrapositivity, if the first player has a winning strategy, then $G$ does not have a perfect matching.