# Name of a game : Remove two chips from a vertex or one chip from both ends of an edge

Consider a finite graph $$\Gamma$$ with a positive number $$n_v\geq 0$$ of chips stacked at each vertex $$v$$ of $$\Gamma$$. Two players play in turn with moves consisting either of removing two chips from a unique vertex $$v$$ such that $$n_v\geq 2$$ or of removing one chip from both endpoints $$v,w$$ of an edge $$\{v,w\}$$ such that $$n_v,n_w\geq 1$$. The first player with no move left loses (or wins when using the misere convention).

The game is trivial on complete graphs. Winning positions have a nice (not completely trivial) description on the graph $$P_3$$ (Dynkin graph of type $$A_3$$) with vertices $$1,2,3$$ and edges $$\{1,2\},\{2,3\}$$: Given a position with $$(a,b,c)$$ chips on vertices $$1,2,3$$, the existence of a winning strategy for the first player and $$a+b+c$$ even (the case $$a+b+c$$ odd is trivial) depends on parities of $$a,b,c$$ and "coarsened" inequalities (coarsened in order to deal with two numbers of different parities) along edges after taking care of "fattened" boundaries.

A similar phenomenon seems to hold for the $$P_4$$ graph and perhaps for all trees.

Has somebody a reference/name for this game?

• More generally, we can allow $\Gamma$ to have loops (edges from a vertex to itself), regarded as having two endpoints. Now the only rule is that we can remove one chip from both endpoints of an edge if the number of chips remains nonnegative at each vertex. Oct 17, 2021 at 14:16
• @RichardStanley I have a slight preference for a formulation without loops : It has a straightforward generalization to simplicial complexes having simplices of dimension at most $d$ : Chose a simplex of dimension $k$ and remove from its $k+1$ vertices $(d+1)!/(k+1)$ chips (if possible). I guess the one-dimensional case of graphs is already quite complicated. Oct 17, 2021 at 20:00
• The case of a path with each $n_v=1$ is equivalent to Dawson's Kayles. I believe this game was first analyzed by Guy and Smith, The $G$-values for various games, Proc. Cambridge Phil. Soc. 52 (1956), 514-526. Oct 17, 2021 at 23:32

In light of Richard Stanley's remark that removing two counters from a vertex $$v$$ may be thought of as removing a counter from both endpoints of a loop at $$v$$, your game seems to be equivalent to Weighted Arc Kayles.