Greography is a game where players take turns naming cities. Each city chosen must begin with the same letter that ended the previous city. The game begins with any starting city and ends when a player loses because he is unable to continue.
This can be modelled with a directed graph $G=(V,E)$ where $(i,j)\in E$ $\Leftrightarrow$ $j$ can be named immediately after $i$.
A subset $M\subseteq M$ is called a matching in $G$ $\Leftrightarrow$ ($v\in V\Rightarrow v$ is incident to at most one edge in $M$). $M$ is called a perfect matching in $G$ $\Leftrightarrow$ $|M|=\frac{|V|}{2}$.
This implies that |V| must consists of an even count of nodes and that each node is incident to exactly one edge in $M$, if $M$ is a perfect matching in $G$.
I'm searching for an explanation why the first player has a winning strategy if and only if $G$ has no perfect matching.
If $M=\left\{(a_i,b_i) : 1\le i\le \frac{|V|}{2}\right\}$, then the player who needs to find a node after $a_i$ for some $i$ can use the matching edge $(a_i,b_i)$ to do so.
However, this is it. So, what's the winning strategy of the first player if $G$ has a perfect matching?
The first player should find a maximum matching of $G$. His first move should be to pick an unmatched vertex(it is possible since the graph has no perfect matching) and every subsequent move should be to pick the vertex matched to the vertex the second player picked. Player two choices are always matched making it possible for player one to have a move. For if they were not, you could find an augmenting path(a path with its internal vertices matched but its ends vertices are unmatched)for the matching through which you could make the matching bigger which is impossible since we started with a maximum matching.