Graph Game: The first player has a winning strategy over a graph $G$ if and only if $G$ has no perfect matching.

Question

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.

Answer 1

We can fix a maximum matching $M$, and then let $v$ be some unmatched vertex. Note $v$ has to exist, as we assumed there is no perfect matching. The first player starts by claiming $v$. Observe that the next vertex $w$ selected must be a matched vertex, otherwise we could extend $M$ to be larger. The first player will respond with the matched neighbor of $w$ in $M$. We can proceed in this fashion until the graph is exhausted, as player $2$ can never claim an unmatched vertex, as this would give an augmenting path that would extend $M$. Hence, Player $1$ has a winning strategy.

Answer 2

Suppose there is no perfect matching and $A$ is a matching of maximum size. Let $V$ be the set of matched vertices of $A$ and $V'$ be the set of unmatched vertices of $A$.

Player one starts by choosing a vertex in $V'$. Then on every turn, if player two took a vertex in $V$, player one takes that vertex's match. (i.e. if player two took $v$ then player one takes $w$ so that $\{v,w\} \in A$)

We claim that if player one follows the above strategy, player two will always select a vertex in $V$.

proof: Suppose towards a contradiction that the above is false. Let $v_i$ be the $i$th vertex selected in the process and suppose that $v_{2k}$ is the first vertex selected by player two that is not in $V$. Then $A \setminus \{\{v_2, v_3\}, \cdots, \{v_{2k-2},v_{2k-1}\}\}$ together with $\{v_1,v_2\}, \{v_2, v_3\}, \cdots, \{v_{2k-1}, v_{2k}\}$ forms a strictly bigger matching than $A$ which is a contradiction.

Thus, player two always selects a vertex in $V$ and player one can always select it's match so player one wins.