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.
2026-05-14 08:50:11.1778748611
Alternatively eliminating vertexes from graph
290 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
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.