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.