Let $G$ by a bipartite graph with parts $X,Y$ both of size $n$. Two players alternately name vertices. P1 names a vertex $a_1$ in X. Then P2 names a vertex $b_1$ in Y which has an edge to $a_1$. Then P1 names a vertex $a_2$ in X which has an edge to $b_1$. And so on. No repetition is allowed and whoever can’t name vertex loses. Show that P2 has a winning strategy when there is a perfect matching in $G$ and P1 has a winning strategy if there isn’t a perfect matching.
I think this should somehow relate to Hall’s marriage theorem, but I’m really lost. Please help.