MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer
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

There are some papers dealing with similar subjects. I googled now:

The second one looks a bit similar to your game.

share|cite|improve this answer
The second paper looks similar but the rules are a bit different. The players remove a vertex and all the neighboring vertices. May be there is a way to map the game in question to the one here. – Uday Apr 24 '12 at 17:02
It seems like your game fits within the class of games the second paper describes as being equivalent to a "domination game": there is a finite set of moves (one for each vertex in the original graph plus one for each edge), a move can only be played once, and the set of available moves at subsequent turns strictly decreases. – Yoav Kallus Apr 24 '12 at 20:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.