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.

verticesis 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