POLYA023: Relation on graphs from games (proposed by Stephen Locke, 11/2/01).

The Game G: Two players select a graph G and then take alternate turns. Set G_0=G, and for move k, the player selects a simple path P_k from G_{k-1} and sets  G_k = G_{k-1} - Edges(P_k). [Note that only the edges of the path are deleted, not the vertices.] The player who takes the last edge wins.  Let G \sim H for two disjoint graphs G and H, if  G \cup H is a loss
for the first player. It is obvious that \sim is reflexive and symmetric. Prove that \sim is also transitive (and, therefore, an equivalence relation).

Discussion. [LZ, 1/5/02]:  Suppose F~G and and G~K and the first player deletes any P_1 from F to get F_1. Then the 2nd player can choose P_2 as follows:
Keep removing paths from G as long as one (and only one in fact) of the (F_1 \cup G_k) and (G_k \cup K) is still a winning graph. Then the winning path for this winning graph must be in F_1 or K. This path is P_2.
It's then easy to verify this is a winning strategy for the 2nd payer.

[SCL, 1/8/02]: When I proposed this problem, I was thinking of it as a potential problem for a Discrete Mathematics type of class, so you're correct that it is easy.
My own solution is only a little longer, and that because I chose to be more wordy. My real question is whether or not anybody has seen this, or a similar result about games.  There is a concept called Grundy labeling, but that doesn't quite seem to fit this situation.
By the way, the game was mentioned by Harary in a talk at LSU (my son attended, but I didn't), in which  Harary asked for a wining strategy for the game when one starts with a caterpillar. A caterpillar is a tree (a connected acyclic graph) such that removing all of the endvertices simultaneously results in (at most) a path. (The resultant graph might be called the "spine".) I catalogued the winning situations for spines with at most four vertices, and one could easily continue to five, six, etc. A general description of the winning moves, a la Nim, wasn't apparent to me.
(I don't know that one should credit Harary, though, since the game is so similar to Hackenbush and its variants. See Conway's books. On the other hand, if  Conway didn't list it, maybe one can say it is new.)

Bibliography.
 
 
 

Return to [Polya Home Page] [Members] [Problem Center] [Inventory] [Reserve Area]