# Game on undirected graphs

One of my friends suggested the following 2-player game.

   Given an undirected graph(not necessarily connected), each player takes turns
and removes either one vertex or two adjacent vertices. Removing a vertex from
the graph consists of deleting the incident edges as well. The player who does
not have any move loses.


Though the rules of the game look very simple, this turns out to be an interesting counting and connectivity game. Infact, using symmetry argument, we have also found that there is a winning strategy for the second player when the undirected graph is merely an even length cycle.

The following are my questions:

Does any graph theory concept suggest this game? Is there a standard game of this sort? Can we come up with a winning strategy for any player for the general graph? My guess is this game may be a version of game of Nim over graphs, I am not sure though.

Thank you.

-

On any graph it is a combinatorial game which can be analyzed by the usual techniques. I can think of a few named cases.

If the graph is a path, it is called Kayles. Having it be a single cycle is the same with the added condition that the first player on their first move must choose from an end.

For a complete graph it is the subtraction game $S(1,2)$

A complete bipartite graph $K_{a,b}$ seems like a natural case.

-
A natural variation on the OP's game is to allow removal of any clique. It would not change the game for paths and cycles. For a union of complete graphs, it would be Nim. –  Yoav Kallus Apr 24 '12 at 20:30