Game on the graph with matchings

Question

The game on the graph $G$ is defined as follows. Initially, the chip is located at one of the vertices (let's call it the starting one). The players take turns, on each move it is necessary to move the piece along any outgoing edge to the vertex, where the piece has never been. The one who cannot make a move loses. How to Prove that the former wins if and only if the starting vertex lies in all maximal matchings?

Answer 1

First of all, let me correct maximal matchings (that is, matchings which cannot be extended) to maximum matchings (that is, matchings of maximal size).

Suppose first that the starting vertex $v$ doesn't lie on all maximum matchings. Pick a maximum matching $M$ which doesn't contain $v$. The second player will always play an edge from $M$ – we will show that this is always possible. Suppose that the game play so far has been $v,a_1,b_1,\ldots,a_t$. We know that $M$ doesn't touch $v$. If it also doesn't touch $a_t$, then this is an augmenting path (check!), which contradicts the maximality of $M$. Hence $M$ must contain an edge $(a_t,b_t)$, which the second player can play.

Suppose next that the starting vertex $v$ does lie on all maximum matchings. Pick some maximum matching $M$ which contains $v$. The first player will always play an edge from $M$. Suppose that the game play so far has been $v,a_1,\ldots,b_t$. If $M$ doesn't touch $b_t$ then we could switch edges according to this "almost-augmenting" path to obtain another maximum matching which doesn't contain $v$. Hence $M$ must contain an edge $(b_t,a_{t+1})$, which the first player can play.