Anna and John play on a graph G, alternatively selecting distinct vertexes from it such that for each i > 0, v[i] is adjacent to v[i−1]. Loses the one who can't select anymore a vertex. Prove that if Anna starts the game, then she will have a winning strategy(it means that no matter how well John will play, she still wins) if and only if the graph G hasn't a perfect matching. Also prove that for a given graph, the problem of deciding whether Anna has a winning strategy(when she starts the game) is from NP.


We assume WLOG that $G$ is connected. For if $G$ is not connected, we simply play on a single connected component and analyze that. So we need to show:

Player $1$ has a winning strategy implies that $G$ has no perfect matching. We do this by contrapositive. So suppose $G$ has a perfect matching. Then $G$ has a one-factor, pairing vertices along the matched edges. Player one chooses a vertex and player two chooses its mate along the matching. Player $2$ will thus win.

Now suppose $G$ has no perfect matching. We need to show that player $1$ has a winning strategy. We do this by contradiction. Let $M$ be a maximum matching of $G$. Let $v_{0} \not \in M$ be the first selected vertex by player one. Since $M$ is a maximum matching, $v_{0}$ is adjacent to some vertex in $M$. Then we have player $2$ choosing such a vertex in $M$. Then player $1$ chooses the adjacent vertex in $M$. This process continues, allowing player $1$ to always move. By assumption, player $2$ won, and so chose the last vertex. However, this vertex sequence would define an $m$-augmenting path, contradicting that $M$ is maximum.

To show that this problem is in $\mathcal{NP}$, we simply check the vertex sequence from the pair $(G, S)$ where $G$ is our graph and $S$ is the tuple of strategies for the players. This can be done in polynomial time.

| cite | improve this answer | |
  • $\begingroup$ Thank you very much! May I ask you to look to the other question I posted yesterday? math.stackexchange.com/questions/1042864/… $\endgroup$ – serban0 Nov 29 '14 at 21:54
  • 1
    $\begingroup$ I saw that thread and can't follow it because of lack of LaTeX. Please edit your post to include the appropriate formatting: math.stackexchange.com/editing-help#latex Also, I'm not sure if I'll have time to slog through the algorithm. $\endgroup$ – ml0105 Nov 29 '14 at 23:06
  • $\begingroup$ Improvements done, please check if everything looks as it should now. $\endgroup$ – serban0 Nov 30 '14 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.