# The game of removing two vertices in a graph

Consider the following impartial combinatorial game played with finite graphs: A move removes two adjacent vertices; and of course all edges connected with them. The game then continues with the new graph. Often this turns out to be disconnected, so we end up in a sum of smaller games. Let us choose the normal play rule (if no move is possible, one loses).

Question. Does this game have a name? Has it been studied anywhere?

It seems to me that Cram is a special case of this game: To each box corresponds a vertex. These are adjacent via some edge iff the boxes are adjacent. This is also mentioned in the 2nd Volume of Winning Ways (by Berlekamp, Guy, Conway), where Cram is turned directly into a game on graphs. The authors mention that we can play arbitrary graphs, but only study grid-like graphs which arise in Cram. The game is also mentioned in the paper Let us play with qubits in section 3.2., denoted "the classical domino game" on graphs, but also restricts to grid-like graphs.

-
I remember a primitive version called "pick up sticks", but I suspect the move and halt conditions were different. Seriously though, have you tried web search terms like "combinatorial games edge removal"? If you search non mathematical game sources under abstract games, you might find something rewarding. Gerhard "Ask Me About System Design" Paseman, 2012.05.26 –  Gerhard Paseman May 26 '12 at 16:55
There is a game on graphs called the "independence game" where the two players alternate turns in removing a vertex and all of its neighbors. The game you suggest with graph $G$ is the special case of this game, when the starting graph is the line dual of the graph $G$. In particular, Dawson's chess is a special case of your game, and this is quite studied! –  M P May 26 '12 at 17:59
@Gerhard: There are the papers "A game of edge removal on graphs" (Gallant, Gunther, Hartnell) and "An edge-removing game on a graph (a generalization of Nim and Kayles)" (Kano). But in the game I've mentioned the removal of the vertices is more important. A game of this type is studied in "Vertex Deletion games with Parity rules" (Nowakowski, Ottaway), but there a move only removes one vertex. –  Martin Brandenburg May 26 '12 at 18:03
I had asked a similar question in: mathoverflow.net/questions/95042/game-on-undirected-graphs. Some of the answers therein may help. –  Uday May 26 '12 at 20:51
@Uday: Yes, again these are only similar games... –  Martin Brandenburg May 27 '12 at 8:15

Per Martin's request, here is a more detailed version of my comment. Given a graph $G$, the independence game is the game in which two players take turn in removing a vertex and all of its neighbors. The game terminates when a player can make no further move, and it is a win for the player who last moved in the normal play and for the other one in the misère play.

The game that Martin suggests with starting graph $G$ is the special case of the independence game, played on the line dual of $G$: the line dual of a graph $G$ is the graph whose vertices are the edges of $G$ and whose edges are pairs of non-disjoint edges of $G$.

In particular, when the initial graph is a path, its line dual is also a path and the game is the same as what is called Dawson's chess. In this case, the independence game on a path with $n$ vertices with normal play, is a second player win if and only if either $n \in \{ 0, 14, 34\}$ or $n \equiv 4, 8, 20, 24, 28 \pmod{34}$.

-
Thanks! I already knew this periodicity of $1 \times n$ Cram, but didn't know that it can be deduced from Dawson's chess - interesting! So do you expect that this game won't have a name or particular analysis because of your reduction? –  Martin Brandenburg May 26 '12 at 20:01
Dear Martin, I do not know if your game already has its own name. The fact that it is a special case of a known game does not imply that it doesn't! The independence game is quite difficult to analyze, as already the case of paths shows. Since paths are also line duals, this might suggest that the "independence game on line duals" is not substantially easier than the general independence game. –  M P May 26 '12 at 20:18
Alright. Then I will wait for other answers, perhaps this game has been already studied. –  Martin Brandenburg May 27 '12 at 8:16

If you haven't already, take a look at "Kayles on the way to the stars" by R. Fleischer, G. Trippen. It is a paper about the analysis of the game of Kayles on graphs, which shouldn't be far from Dawson's Kayles on graphs, which is similar to what you're looking for. Please note that the authors adopted the rule of removing nodes rather than edges.

-
This is what MP called the "independence game": A vertex together with all its neighbors are removed. This is not the game I'm asking for (although, it can be reduced to that, as MP pointed out). They also consider the variant of removing $1$ or $2$ vertices (adjacent). But in my version, exactly $2$ have to be removed. –  Martin Brandenburg May 29 '12 at 13:07