Parity conjecture for trees

An eleven-edge spider disproves the tree-parity conjecture for the Game of Cycles

Robbert Fokkink and Jonathan Zandee formulate the following statement as Conjecture 1 of Some remarks on the Game of Cycles: for every tree $T$, its Game-of-Cycles Sprague--Grundy value satisfies

$$g(T)=0 \quad\Longleftrightarrow\quad |E(T)|\equiv0\pmod 2. \tag{1}$$

Here, exactly as stipulated in their paper, every degree-one vertex is special, so all edges of the tree are initially markable. The three-legged spider with leg lengths $1,3,7$ is a counterexample: it has eleven edges but Grundy value zero.

1. The exact game and its finite mathematical recurrence

Let $T$ be a finite tree. A position is a partial orientation $\sigma$ of its edges. A move orients exactly one previously unoriented edge. At each internal vertex, it is forbidden to orient the last incident edge in a manner that creates a source or sink. Equivalently, $\sigma$ is legal precisely when every internal vertex whose incident edges are all oriented has at least one incoming and at least one outgoing edge. Leaves are exempt from this condition.

Write $\mathcal F(\sigma)$ for the set of legal partial orientations obtained from $\sigma$ by orienting one additional edge. The source's normal-play Grundy recurrence is

$$g(\sigma) =\operatorname{mex}\{g(\tau):\tau\in\mathcal F(\sigma)\}. \tag{2}$$

In particular, $g(\sigma)=0$ for a terminal position. Since each move increases the number of oriented edges, (2) is a finite, exact backward induction with no supplementary game assumptions.

Reversing every directed edge preserves legality, the follower relation, and terminal positions. Consequently, for every partial orientation,

$$g(-\sigma)=g(\sigma). \tag{3}$$

Thus the two opposite orientations of any first edge have the same Grundy value.

2. The explicit odd-edge losing tree

Let $o$ be the unique vertex of degree three, and attach to it three internally disjoint paths of lengths $1$, $3$, and $7$:

$$\begin{aligned} o&-a_1,\\ o&-b_1-b_2-b_3,\\ o&-c_1-c_2-c_3-c_4-c_5-c_6-c_7. \end{aligned} \tag{4}$$

The tree has

$$|V(T)|=12, \qquad |E(T)|=1+3+7=11. \tag{5}$$

For an edge on a leg of length $\ell$, let $j$ be its distance from $o$, with $j=1$ for the edge incident to $o$. Direct evaluation of the complete legal-position recurrence (2) gives the following Grundy values after the first edge is oriented. By (3), each entry applies to both possible directions.

$$\begin{array}{c|c|c} \text{leg length }\ell&\text{edge distance }j& \text{Grundy value after that first move}\\ 1&1&2\\ 3&1&2\\ 3&2&6\\ 3&3&6\\ 7&1&6\\ 7&2&6\\ 7&3&6\\ 7&4&4\\ 7&5&6\\ 7&6&4\\ 7&7&8 \end{array} \tag{6}$$

For completeness, the entire legal state space has $27737$ partial orientations. Grouping them by the number $r$ of oriented edges gives the exact finite certificate

$$\begin{array}{c|rrrrrrrrrrrr} r&0&1&2&3&4&5&6&7&8&9&10&11\\ \#\text{ legal states} &1&22&204&1042&3220&6240&7634&5828&2706&730&104&6. \end{array} \tag{7}$$

These are precisely the partial orientations satisfying the internal source/sink condition; every such orientation is reachable, because deleting oriented edges cannot create a complete internal source or sink. Applying (2) successively from larger $r$ to smaller $r$ yields (6).

Every entry in (6) is nonzero. Therefore every legal first move is winning for the next player, and the initially unoriented position satisfies

$$g(T) =\operatorname{mex}\{2,4,6,8\} =0. \tag{8}$$

Combining (5) and (8),

$$|E(T)|=11\equiv1\pmod2, \qquad g(T)=0, \tag{9}$$

contradicting (1).

3. Why the earlier three-legged-spider theorem does not already give this counterexample

Bryant G. Mathews's earlier The Game of Arrows on 3-Legged Spider Graphs distinguishes the original game, where a leaf edge cannot be marked, from the trimmed game, where leaves are special and all remaining edges are markable. Trimming shortens every leg of a spider by one.

His Theorem 12.1 proves that a trimmed spider is losing when all three trimmed leg lengths are even. Equivalently, his headline statement concerns an original, untrimmed spider whose three legs all have odd lengths. Fokkink and Zandee explicitly cite this result in its trimmed, even-leg form.

The tree (4), by contrast, already uses the trimmed convention of their conjecture and has three odd leg lengths $1,3,7$. It corresponds before trimming to leg lengths $2,4,8$, which are outside Mathews's odd-untrimmed-leg theorem. Thus (9) is a counterexample to the conjectured parity rule under its own precise special-leaf convention, not an application or restatement of the earlier even-leg result.