We have a graph $G = (V,E)$. Two players are playing a game in which they are alternately selecting edges of $G$ such that in every moment all the selected edges are forming a simple path (path without cycles).
Prove that if $G$ contains a perfect matching, then the first player can win. A player wins when the other player is left with edges that would cause a cycle.
I tried with saying that $M$ is a set of edges from perfect matching and then dividing the main problem on two sub problems where $M$ contains an odd or even number of edges, but it lead me nowhere. Please help.
Bipartition the vertices according to the perfect matching into sets $A$ and $B$. The first player plays an edge of the matching; the second player cannot. However, since this is not a cycle, we are at a new vertex, so the first player can again play an edge from the matching. He can continue this way until all of the edges in the perfect matching are gone. This involves all of the vertices, so the next edge must form a cycle.