# Analyzing a class of vertex-deletion games

As part of the discussion on this question (Permutation Game Redux), a simple vertex-deletion game was proposed. The game is very simple.

Disconnect. Players alternately remove vertices from a graph $G$. The player that produces a fully disconnected graph (i.e., a graph with no edges) is the winner.

Because the game is impartial, the Sprague-Grundy theory applies: each game is equivalent to a nim-heap of some size (its nim-value), which can be calculated as the mex (minimum excluded nim-value) of its options. These nim-values can then be used to compute the nim-values of disjunctive sums of games in the usual way.

One would like to apply this theory within a single game, e.g., to break a graph into its connected components, calculate their nim-values, and then combine them to find the value of the overall graph. Unfortunately, this doesn't work. The problem is that the win condition is not standard: the game ends before all moves are exhausted (or, equivalently, the allowed moves in one component of the graph depend on the other components).

It is not hard to see that for any graph $G$ and any even $n$, the game $G \cup \bar{K}_n$ is equivalent to $G$ (where $\bar{K}_n$ is the edgeless graph on $n$ vertices). To prove it, we need to show that the disjunctive sum $G + G\cup\bar{K}_n$ is a second-player win. The proof is by induction on $|G|+n$. If $G$ is edgeless, then the first player loses immediately (both games are over). Otherwise, the first player can move in either $G$, and the second player can copy his move in the other one (reducing to $G' + G'\cup \bar{K_n}$ with $|G'|=|G|-1$); or, if $n\ge 2$, the first player can move in the disconnected piece, and the second player can do the same (reducing to $G + G\cup\bar{K}_{n-2}$).

This shows that any graph $G$ is equivalent to $H \cup K_p$, where $H$ is the part of $G$ with no disconnected vertices, and $p=0$ or $1$ is the parity of the number of disconnected vertices in $G$. All games in an equivalence class have the same nim-value, and moreover, the equivalence relation respects the union operation: if $G \sim H \cup K_p$ and $G' \sim H' \cup K_{p'}$ then $G \cup G' \sim (H \cup H')\cup K_{p\oplus p'}$. Moreover, one can see that the games in $[H \cup K_0]$ and $[H \cup K_1]$ have different nim-values unless $H$ is the null graph: when playing $H + H \cup K_1$, the first player can take the isolated vertex, leaving $H+H$, and then copy the second player's moves thereafter.

Beyond this, are there any other general decomposition or equivalence results? Any extension of the Sprague-Grundy theory to this class of games? In particular, is there some more refined equivalence relation still to be found such that all games in $[G]$ have the same nim-value, and $[G \cup H]$ can be determined in terms of $[G]$ and $[H]$?

-
Your insight generalizes to all connected components, not just disconnected vertices. The game is completely determined by the parities of the numbers of instances of all types of connected components; adding two isomorphic connected components leads to an equivalent game, since you can always play in one when the other player plays in the other, until they're reduced to an even number of disconnected vertices, which you've handled. – joriki Jan 3 '12 at 0:03
@joriki: I thought that initially as well, but in fact it's not the case. As a counterexample, consider the graph $K_1 \cup G \cup G$, where $G$ is not edgeless. Your argument suggests that this should be equivalent to $K_1$, which is a second-player win (since it is disconnected, there are no more moves allowed). But in fact the first player has a winning strategy: first delete the $K_1$, producing $G \cup G$, and then copy the second player's moves. In other words, $K_1 = 0$ and $G \cup G = 0$, but $K_1 \cup (G \cup G) \neq K_1 + (G \cup G)$. – mjqxxxx Jan 3 '12 at 3:59
I see -- interesting -- the supposed proof of equivalence fails because it's not always possible to mirror moves because, as you wrote, a move's admissibility depends on the other components, and it works in your special case because disconnected vertices are the only type of components that don't affect admissibility. – joriki Jan 3 '12 at 8:02