# algorithms – Game on the graph with matchings

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?