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](http://en.wikipedia.org/wiki/Cram_%28game%29) 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](http://arxiv.org/pdf/quant-ph/0311018v1.pdf) in section 3.2., denoted "the classical domino game" on graphs, but also restricts to grid-like graphs.



The game of removing two vertices in a graph
Per Martin's request, here is a more detailed version of my comment. Given a graph $G$, the [independence game](http://www.jstor.org/stable/3619902?seq=1) 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}$.


