<p>I post an update as a self-answer only to keep it distinct from the question (<em>which is still open</em>).</p>

<p>As shown in the comments (thanks to Tsuyoshi Ito) the problem is polynomial-time solvable for paths:</p>

<p>$Win(P_n) = 1$ iif $(n \bmod 34) \in \{3,7,23,27\}$</p>

<p>Starting from 0, the (calculated) sequence of the nim values is periodic:</p>

<pre><code>0,1,1,0,2,1,3,0,1,1,3,2,2,3,4,1,5,3,2,2,3,1,1,0,3,1,2,0,1,1,4,4,2,6,
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6,
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6,
...
the subsequence rseq of length 34:
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6
is repeated
</code></pre>

<p>I didn't work on a rigorous mathematical proof, but the idea is:</p>

<p>suppose that we want to calculate element $Win(P_n), n = k*34 + x \; (k\geq 4, 0 \leq x &lt; 34)$, then the first move (pick an edge) can split the path in $\lceil n / 2 \rceil$  different ways (n-2,0),(n-3,1),(n-4,2),...). The new nim value is equal to:</p>

<p>$mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{\lceil n / 2 \rceil}+P_{n-\lceil n / 2 \rceil}\}$</p>

<p>The first 34 elements of the set are produced by the first non repeating sequence (0,1,1,0,...) (nim)summed with the elements of the repeating sequence in reverse order starting from element $(34-2-x) \bmod 34$.</p>

<p>For example: for $x = 0$:</p>

<pre><code>     0,1,1,0,2,1,3,0,1,1,3,2,2,3,4,1,5,3,2,2,3,1,1,0,3,1,2,0,1,1,4,4,2,6 +
     3,4,4,1,1,0,2,1,3,0,1,1,3,2,2,7,5,4,4,3,2,2,3,1,1,0,3,1,2,0,1,1,4,6 =
mex{ 3,5,5,1,3,1,1,1,2,1,2,3,1,1,6,6,0,7,6,1,1,3,2,1,2,1,1,1,3,1,5,5,6,0 } = 4
</code></pre>

<p>For x=0..33 the resulting mex sequence is equal to the repeating sequence:</p>

<pre><code>4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6
</code></pre>

<p>The remaining elements of the set are calulated only on the repeating sequence(s): $rseq[j \bmod 34] + rseq[(34-2-x-j) \bmod 34]$ (for $j \geq 34$ the pairs are repeated, so they don't alter the mex result). The resulting mex sequence for x=0..33 is:</p>

<pre><code>4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,4,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,4,
</code></pre>

<p>Which is equal to the repeating sequence except for $x=16$ and $x=33$; but the values are lower than the corresponding mex on the non-repeating sequence, so: </p>

<p>$mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{\lceil n / 2 \rceil}+P_{n-\lceil n / 2 \rceil}\}$ = $mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{n-2-33}+P_{33}\}$</p>

<p>and for $(k\geq 4, 0 \leq x &lt; 34)$, $Win(P_{k*34 + x}) = Win(P_{34+x}) = Win(P_x)\; $</p>

CC BY-SA 3.0
2013-02-01T11:11:44.287Z
According to my calculation, the first player does have a winning strategy for $P_{23}$, giving a counter-example to your claim $Win(P_n)= 1$ iff $(n \mod\, 34) \in \{3, 7, 23, 27\}$.
user13136
CC BY-SA 3.0
2013-02-01T11:48:17.530Z
@user13136: did you check the nim values? For $P_{23}$ the nim value is 0 (I got the same values of Tsuyoshi with a different program, but perhaps we are both wrong).
Marzio De Biasi
CC BY-SA 3.0
2013-02-01T15:48:51.520Z
I think a possible flaw in your programs could be the ignoring of the $P_0$, in which case the first player always loses. If you want, we can play the case $P_{23}$ now.
user13136
CC BY-SA 3.0
2013-02-01T18:16:09.597Z
Sorry, I have to leave now.
user13136
CC BY-SA 3.0
2013-02-01T18:45:57.673Z
$(n_{17}, n_{18}) \to (n_{5}, n_{6}) \to (n_{11}, n_{12}) \to (n_{1}, n_{2})$ (you can delete the previous comments containing the moves)
Marzio De Biasi
CC BY-SA 3.0
2013-02-02T21:54:25.170Z
I am very very sorry: The flaw is mine. Your claim seems to be true.
user13136
CC BY-SA 3.0
2013-02-02T22:46:59.170Z
@user13136: don't worry: I don't trust my programs too much, so it was you and me against my poor java code ... it won :-)
Marzio De Biasi
CC BY-SA 3.0
2013-01-28T22:43:34.980Z
2013-01-29T04:52:22.030Z
2013-01-29T04:52:22.030Z
Marzio De Biasi
<p>Is this perfect information game played on graphs know/studied?</p>

<blockquote>
Given a graph $G= (V,E)$, two players alternate picking an edge <em>or</em> an isolated node. If the player picks an edge $e = (u,v)$ the two nodes $u$ and $v$ are deleted along with their incident edges. If the player picks an isolated node, the node is deleted. The first player unable to move loses the game.
</blockquote>

<p>What is the complexity of finding the winner?</p>

<p>Any references to similar games?</p>

CC BY-SA 3.0
2013-01-26T10:00:09.043Z
I didn't think about it too much (still waiting for a quick answer), but it is in PSPACE; for $K_n$ the winner is $|E| \mod 2$, for paths with even length the winner is player 0, ...
Marzio De Biasi
CC BY-SA 3.0
2013-01-26T13:42:04.570Z
I assume the isolated node is removed if picked? If so, player 0 wins also on all nonempty paths by spending the first move subdividing the problem into two equal components and then mirroring the opponents move on the opposite component from then onward to maintain isomorphism. This implies player 1 wins on a cycle, since the first move reduces the problem to a path.
Yonatan N
CC BY-SA 3.0
2013-01-26T20:02:48.600Z
@YonatanN: yes an isolated node can be picked (and removed); but the simmetry strategy works on paths of even length (player 0 picks the 2 central nodes as first move, then mirrors the moves of player 1), but not on the paths of odd length: try to apply the strategy to a path of length 11, and it doesn't work (indeed for a path of length 11 the winner is player 1).
Marzio De Biasi
CC BY-SA 3.0
2013-01-26T20:17:11.893Z
You're right. I overlooked the requirement for the individually-selected node to be isolated right after asking about just that. My mistake.
Yonatan N
CC BY-SA 3.0
2013-01-27T15:35:41.813Z
@Marzio De Biasi: That is a nice game! Could you please explain why for the path on 11 nodes, P11, player 1 always wins? Thank you.
user13136
CC BY-SA 3.0
2013-01-27T15:51:42.987Z
@MarzioDeBiasi: I'm a bit confused. When you refer to the length of a path, do you mean the number of edges, or the number of vertices?  For an n-vertex complete graph, if I understand correctly, no matter how the players move, the total number of moves is $\lfloor n/2 \rfloor$ because from $K_n$ one move results in $K_{n-2}$. So, the parity of this number should give a winner. But this doesn't look the same as $|E|$ mod 2.
Yoshio Okamoto
CC BY-SA 3.0
2013-01-27T15:55:30.703Z
@user13136: using a simple program that checks all the moves :-)
Marzio De Biasi
CC BY-SA 3.0
2013-01-27T16:04:01.640Z
@YoshioOkamoto: sorry I was a little bit imprecise: player 0 has a winning strategy on every path with an *even number of nodes* (i.e. odd length): he picks the 2 central nodes and then "mirrors" the moves of player 1, in this way he always pick the last node (or edge) and wins. You're also right for the $K_n$ graphs: the winner is $\lfloor n / 2 \rfloor \mod 2$ ... (I had the strategy in mind but I wrote the first comment too quickly) :(
Marzio De Biasi
CC BY-SA 3.0
2013-01-27T17:06:57.247Z
@Marzio De Biasi: I am sorry but when I play nice games I normally play by hand. Unless I made mistakes, player 0 does have a winning strategy:
Observe that: a) for P1, P2, P5, and P8, player 0 always  wins. 
b) for  P3 and P7, player 1 always wins. 
c) for P4 and P6, player 0 can decide to win or to lose.
Now in case of P11:
 - Number the nodes of P11 with v1, v2, ... v11.
 - Player 0 takes the edge v9, v10 and the rest is the isolated node v11 
and P8. If player 1 takes v11, player 0 will win because he has an even path. 
Otherwise, player 0 will win by a), b) and c).
user13136
CC BY-SA 3.0
2013-01-27T18:35:10.017Z
@user13136: you are right the winner of P11 is player 0! I forgot that the program checks the startegies of slightly different game :(
Marzio De Biasi
CC BY-SA 3.0
2013-01-27T23:12:21.967Z
According to my [program](http://ideone.com/P7fu89), the values of n≤100 such that the first player loses in the game on the path with n vertices are 3, 7, 23, 27, 37, 41, 57, 61, 71, 75, 91, and 95.  Unfortunately, I do not see any pattern other than being odd (which was already known), and [OEIS](http://oeis.org/) does not show any matches.
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-27T23:51:24.223Z
@TsuyoshiIto: ... take the pairwise difference: (3 7) (23 27) (37 41) (57 61) (71 75) (91 95) and you get 4 4 4 4 4 4 ... it seems a pattern :-) .... (3 ... 23) ... (37 ... 57) ... (71 ... 91) and you get 20 20 20 ... another one! :-D
Marzio De Biasi
CC BY-SA 3.0
2013-01-28T00:02:20.667Z
@MarzioDeBiasi: Thank you for the clarification.  I had a typo: $\lfloor n/2 \rfloor$ should be $\lceil n/2 \rceil$.
Yoshio Okamoto
CC BY-SA 3.0
2013-01-28T00:07:43.037Z
... now it's too late, but tomorrow I'll try if the pattern continues: (3 ... 37) ... (71 ... (105 109) (125 129))
Marzio De Biasi
CC BY-SA 3.0
2013-01-28T00:13:43.793Z
Wow, that is a great observation!  It seems that the numbers in this sequence are exactly the numbers congruent to 3, 7, 23, or 27 modulo 34.  The nim-values seem to be also periodic: starting from n=1, the nim-values are 1, 1, 0, 2, 1, 3, 0, 1, 1, 3, 2, 2, 3, 4, 1, 5, 3, 2, 2, 3, 1, 1, 0, 3, 1, 2, 0, 1, 1, 4, 4, 2, [6, 4, 1, 1, 0, 2, 1, 3, 0, 1, 1, 3, 2, 2, 3, 4, 4, 5, 7, 2, 2, 3, 1, 1, 0, 3, 1, 2, 0, 1, 1, 4, 4, 3], where […] is the seemingly periodic part of length 34.  I think that it should be possible to prove this pattern mostly by calculation.
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-28T18:23:08.057Z
@TsuyoshiIto: great! ... another thing to notice is that in the nim sequence the values 4,1,1,0,2,1,3,0,1,1,3,2,2 are mirrored after 3,4,4,5,7: ... 2,2,3,1,1,0,3,1,2,0,1,1,4
Marzio De Biasi
CC BY-SA 3.0
2013-01-28T22:47:15.667Z
@TsuyoshiIto. I posted the results of the discussion as a (rather fuzzy) answer just to keep the attention to the general problem (it is not too distant from Node Kayles on graphs, so I suspect that it is PSPACE complete)
Marzio De Biasi
<reference-request><combinatorial-game-theory>
Winning strategy of an "edge or isolated vertex" deletion game
Marzio De Biasi
# Winning strategy of an "edge or isolated vertex" deletion game

(Asked by: username_0 on 2013-01-25)

Is this perfect information game played on graphs know/studied?

> Given a graph $G= (V,E)$, two players alternate picking an edge *or* an isolated node. If the player picks an edge $e = (u,v)$ the two nodes $u$ and $v$ are deleted along with their incident edges. If the player picks an isolated node, the node is deleted. The first player unable to move loses the game.

What is the complexity of finding the winner?

Any references to similar games?

**Tags:** reference-request, combinatorial-game-theory
> **Comments:**
> **username_0**: I didn't think about it too much (still waiting for a quick answer), but it is in PSPACE; for $K_n$ the winner is $|E| \mod 2$, for paths with even length the winner is player 0, ...  
> **username_1**: I assume the isolated node is removed if picked? If so, player 0 wins also on all nonempty paths by spending the first move subdividing the problem into two equal components and then mirroring the opponents move on the opposite component from then onward to maintain isomorphism. This implies player 1 wins on a cycle, since the first move reduces the problem to a path.  
> **username_0**: @YonatanN: yes an isolated node can be picked (and removed); but the simmetry strategy works on paths of even length (player 0 picks the 2 central nodes as first move, then mirrors the moves of player 1), but not on the paths of odd length: try to apply the strategy to a path of length 11, and it doesn't work (indeed for a path of length 11 the winner is player 1).  
> **username_1**: You're right. I overlooked the requirement for the individually-selected node to be isolated right after asking about just that. My mistake.  
> **username_2**: @Marzio De Biasi: That is a nice game! Could you please explain why for the path on 11 nodes, P11, player 1 always wins? Thank you.  
> **username_3**: @MarzioDeBiasi: I'm a bit confused. When you refer to the length of a path, do you mean the number of edges, or the number of vertices?  For an n-vertex complete graph, if I understand correctly, no matter how the players move, the total number of moves is $\lfloor n/2 \rfloor$ because from $K_n$ one move results in $K_{n-2}$. So, the parity of this number should give a winner. But this doesn't look the same as $|E|$ mod 2.  
> **username_0**: @user13136: using a simple program that checks all the moves :-)  
> **username_0**: @YoshioOkamoto: sorry I was a little bit imprecise: player 0 has a winning strategy on every path with an *even number of nodes* (i.e. odd length): he picks the 2 central nodes and then "mirrors" the moves of player 1, in this way he always pick the last node (or edge) and wins. You're also right for the $K_n$ graphs: the winner is $\lfloor n / 2 \rfloor \mod 2$ ... (I had the strategy in mind but I wrote the first comment too quickly) :(  
> **username_2**: @Marzio De Biasi: I am sorry but when I play nice games I normally play by hand. Unless I made mistakes, player 0 does have a winning strategy: Observe that: a) for P1, P2, P5, and P8, player 0 always  wins.  b) for  P3 and P7, player 1 always wins.  c) for P4 and P6, player 0 can decide to win or to lose. Now in case of P11:  - Number the nodes of P11 with v1, v2, ... v11.  - Player 0 takes the edge v9, v10 and the rest is the isolated node v11  and P8. If player 1 takes v11, player 0 will win because he has an even path.  Otherwise, player 0 will win by a), b) and c).  
> **username_0**: @user13136: you are right the winner of P11 is player 0! I forgot that the program checks the startegies of slightly different game :(  
> **username_4**: According to my [program](http://ideone.com/P7fu89), the values of n≤100 such that the first player loses in the game on the path with n vertices are 3, 7, 23, 27, 37, 41, 57, 61, 71, 75, 91, and 95.  Unfortunately, I do not see any pattern other than being odd (which was already known), and [OEIS](http://oeis.org/) does not show any matches.  
> **username_0**: @TsuyoshiIto: ... take the pairwise difference: (3 7) (23 27) (37 41) (57 61) (71 75) (91 95) and you get 4 4 4 4 4 4 ... it seems a pattern :-) .... (3 ... 23) ... (37 ... 57) ... (71 ... 91) and you get 20 20 20 ... another one! :-D  
> **username_3**: @MarzioDeBiasi: Thank you for the clarification.  I had a typo: $\lfloor n/2 \rfloor$ should be $\lceil n/2 \rceil$.  
> **username_0**: ... now it's too late, but tomorrow I'll try if the pattern continues: (3 ... 37) ... (71 ... (105 109) (125 129))  
> **username_4**: Wow, that is a great observation!  It seems that the numbers in this sequence are exactly the numbers congruent to 3, 7, 23, or 27 modulo 34.  The nim-values seem to be also periodic: starting from n=1, the nim-values are 1, 1, 0, 2, 1, 3, 0, 1, 1, 3, 2, 2, 3, 4, 1, 5, 3, 2, 2, 3, 1, 1, 0, 3, 1, 2, 0, 1, 1, 4, 4, 2, [6, 4, 1, 1, 0, 2, 1, 3, 0, 1, 1, 3, 2, 2, 3, 4, 4, 5, 7, 2, 2, 3, 1, 1, 0, 3, 1, 2, 0, 1, 1, 4, 4, 3], where […] is the seemingly periodic part of length 34.  I think that it should be possible to prove this pattern mostly by calculation.  
> **username_0**: @TsuyoshiIto: great! ... another thing to notice is that in the nim sequence the values 4,1,1,0,2,1,3,0,1,1,3,2,2 are mirrored after 3,4,4,5,7: ... 2,2,3,1,1,0,3,1,2,0,1,1,4  
> **username_0**: @TsuyoshiIto. I posted the results of the discussion as a (rather fuzzy) answer just to keep the attention to the general problem (it is not too distant from Node Kayles on graphs, so I suspect that it is PSPACE complete)  

---

## 1 answers

### Answer by username_0 on 2013-01-28. Score: 2

I post an update as a self-answer only to keep it distinct from the question (which is still open).
As shown in the comments (thanks to Tsuyoshi Ito) the problem is polynomial-time solvable for paths:
$Win(P_n) = 1$ iif $(n \bmod 34) \in \{3,7,23,27\}$
Starting from 0, the (calculated) sequence of the nim values is periodic:
0,1,1,0,2,1,3,0,1,1,3,2,2,3,4,1,5,3,2,2,3,1,1,0,3,1,2,0,1,1,4,4,2,6,
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6,
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6,
...
the subsequence rseq of length 34:
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6
is repeated

I didn't work on a rigorous mathematical proof, but the idea is:
suppose that we want to calculate element $Win(P_n), n = k*34 + x \; (k\geq 4, 0 \leq x < 34)$, then the first move (pick an edge) can split the path in $\lceil n / 2 \rceil$  different ways (n-2,0),(n-3,1),(n-4,2),...). The new nim value is equal to:
$mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{\lceil n / 2 \rceil}+P_{n-\lceil n / 2 \rceil}\}$
The first 34 elements of the set are produced by the first non repeating sequence (0,1,1,0,...) (nim)summed with the elements of the repeating sequence in reverse order starting from element $(34-2-x) \bmod 34$.
For example: for $x = 0$:
     0,1,1,0,2,1,3,0,1,1,3,2,2,3,4,1,5,3,2,2,3,1,1,0,3,1,2,0,1,1,4,4,2,6 +
     3,4,4,1,1,0,2,1,3,0,1,1,3,2,2,7,5,4,4,3,2,2,3,1,1,0,3,1,2,0,1,1,4,6 =
mex{ 3,5,5,1,3,1,1,1,2,1,2,3,1,1,6,6,0,7,6,1,1,3,2,1,2,1,1,1,3,1,5,5,6,0 } = 4

For x=0..33 the resulting mex sequence is equal to the repeating sequence:
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6

The remaining elements of the set are calulated only on the repeating sequence(s): $rseq[j \bmod 34] + rseq[(34-2-x-j) \bmod 34]$ (for $j \geq 34$ the pairs are repeated, so they don't alter the mex result). The resulting mex sequence for x=0..33 is:
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,4,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,4,

Which is equal to the repeating sequence except for $x=16$ and $x=33$; but the values are lower than the corresponding mex on the non-repeating sequence, so: 
$mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{\lceil n / 2 \rceil}+P_{n-\lceil n / 2 \rceil}\}$ = $mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{n-2-33}+P_{33}\}$
and for $(k\geq 4, 0 \leq x < 34)$, $Win(P_{k*34 + x}) = Win(P_{34+x}) = Win(P_x)\; $

> **Comments:**
> **username_2**: According to my calculation, the first player does have a winning strategy for $P_{23}$, giving a counter-example to your claim $Win(P_n)= 1$ iff $(n \mod\, 34) \in \{3, 7, 23, 27\}$.  
> **username_0**: @user13136: did you check the nim values? For $P_{23}$ the nim value is 0 (I got the same values of Tsuyoshi with a different program, but perhaps we are both wrong).  
> **username_2**: I think a possible flaw in your programs could be the ignoring of the $P_0$, in which case the first player always loses. If you want, we can play the case $P_{23}$ now.  
> **username_2**: Sorry, I have to leave now.  
> **username_0**: $(n_{17}, n_{18}) \to (n_{5}, n_{6}) \to (n_{11}, n_{12}) \to (n_{1}, n_{2})$ (you can delete the previous comments containing the moves)  
> **username_2**: I am very very sorry: The flaw is mine. Your claim seems to be true.  
> **username_0**: @user13136: don't worry: I don't trust my programs too much, so it was you and me against my poor java code ... it won :-)  

---

