# A theoretical expansion of the Sprout game

Soura Sena Das$\,{}^{a}$, Zin Mar Myint$\,{}^{b}$, Soumen Nandi$\,{}^{c}$,
Sagnik Sen$\,{}^{b}$, Éric Sopena$\,{}^{d}$

$(a)$ Indian Statistical Institue, Kolkata, India.
$(b)$ Indian Institute of Technology Dharwad, India.
$(c)$ Institute of Engineering and Management, Kolkata, India.
$(d)$ Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400, Talence,
France

###### Abstract

Sprout is a two-player pen and paper game which starts with $n$ vertices, and
the players take turns to join two pre-existing dots by a subdivided edge
while keeping the graph sub-cubic planar at all times. The first player not
being able to move loses. A major conjecture claims that Player 1 has a
winning strategy if and only if $n\equiv 3,4,5$ ($\bmod~{}6$). The conjecture
is verified until $44$, and a few isolated values of $n$, usually with the
help of a computer. However, to the best of our understanding, not too much
progress could be made towards finding a theoretical proof of the conjecture
till now.

In this article, we try to take a bottom-up approach and start building a
theory around the problem. We start by expanding a related game called
Brussels Sprout (where dots are replaced by crosses) introduced by Conway,
possibly to help the understanding of Sprout. In particular, we introduce and
study a generalized version of Brussels Sprout where crosses are replaced by a
dot having an arbitrary number of “partial edges” (say, general cross) coming
out, and planar graphs are replaced by any (pre-decided) hereditary class of
graphs. We study the game for forests, graphs on surfaces, and sparse planar
graphs. We also do a nimber characterization of the game when the hereditary
class is taken to be triangle-free planar graphs, and we have started the game
with two arbitrary generalized crosses. Moreover, while studying this
particular case, we naturally stumble upon a circular version of the same game
and solve a difficult nimber characterization using the method of structural
induction. The above mentioned proof may potentially be one approach to
solving the Sprout conjecture.

Keywords: Sprout, impartial game, nimber, planar graph, surfaces.

##  1 Introduction

In 1967, Conway and Paterson [11] introduced the two-player pen and paper game
called Sprout. The game starts with $n$ dots (vertices) on paper, and the
players make their moves alternately. A valid move consists of connecting any
dot to itself or to another dot with a curve (edge) and then placing a new dot
on the curve drawn (subdivision). There are two conditions that need to be
maintained during a move: the curve should not cross itself or any other curve
(planarity), and a spot can have at most three curves incident to it (degree
three). The first player that cannot make a move, loses (see Fig. 1 for an
example). An enigmatic famous conjecture claims the winning strategy in this
game [3].

######  Conjecture 1.1.

If the game of Sprout starts with $n$ dots, then Player $1$ has a winning
strategy if and only if $n\equiv 3,4,5\ (\bmod\ 6)$.

To date, it has been possible to verify the correctness of the conjecture when
the initial number of spots is $n\in\\{1,2,\cdots,44,46,47,53\\}$ (see [6]).
The verifications done are mostly using brute force case analysis [4], and
computer checks [3]. Therefore, finding theoretical tools to attack the
conjecture is a natural open question. There have been a few approaches to
attack the conjecture which can be summarized in few major points.

  * •

A brute force analysis of the game starting with $n$ points: theoretical case
analysis by hand [2] for small values of $n$, and computer checks for large
values of $n$ [3]. The computer checks for larger values of $n$ were helped by
smart theoretical tricks involving the analysis of nimber values for partially
played games [15, 16].

  * •

Interesting properties of the game are explored in [6, 9, 10, 13]. Moreover, a
AI-based game play of Sprouts is developed in [8] which can play the game
perfectly up to $11$ spots (initial condition).

  * •

The game Sprout was introduced as a game played on the plane (or the sphere)
surface. Later the game was extended and analysed for general surfaces, that
is, orientable and non-orientable surfaces having genus $g\geq 0$ [14, 16].

  * •

Analysis of similar games such as Brussels Sprout [5, 7] and Planted Brussels
Sprout [12, 19]. This approach finds its relevance by expressing partially
played games.

Our approach is a blend of analysing similar games from the theoretical
perspective, and thereby extending the knowledge base, and also by analysing
the nimber of such games. Moreover, we present a nimber characterization of a
non-trivial game using the method of structural induction, showing how it can
become a potential tool to attack Conjecture 1.1.

Figure 1: An example of Sprout game.

######  Remark 1.2.

There are several instances in the history of graph theory and combinatorics
research where a rich theory developed while attempting to build tools for
solving a particularly challenging open problem. For example, in attempt to
solve the Four-Color Theorem researchers developed important concepts of graph
theory including vertex coloring, edge coloring, and chromatic polynomials
[18]. In the field of combinatorial games, the study and analysis of the game
Nim gave rise to the theory of impartial games [1]. It is noteworthy, that the
game Sprout is also an impartial game. This paper attempts to initiate such a
bottom up approach to develop a theory around the game of Sprout. Our initial
approach is to generalize and analyze the study of a related, and better
understood game called Brussels sprout introduced by Conway [5].

###  1.1 A generalization of the Brussels sprout game

Conway [11] introduced a variation of Sprout, called Brussels sprout, possibly
as a potential way to approach the study of Sprout. This is also a two player
pen and paper game where, instead of dots, we start with $n$ crosses. Each
cross has four open arms or open tips and a player can only connect the open
tips. So a valid move consists of connecting any two open tips with a curve,
and a crossbar is placed on the newly made curve. The crossbar creates two new
open tips which can be used in subsequent moves. This game also retains the
restriction of the curves not crossing each other (planarity) during the play
from Sprout. As a two-player game, each player makes their move on alternate
turns, and the first player who cannot make a valid move loses. However, in
this case, using Euler’s formula for planar graphs, one can easily figure out
the player having a winning strategy. In fact, the moves made by the players
are redundant, and no matter how they play, the total number of moves and the
winner of the game is a function of the number $n$ of the initial crosses only
(see Fig. 2 for an example).

In this article, we look into a generalized version of Brussels sprout, where
instead of crosses we have a variable number of open tips for each spot. A set
of graphs $\mathcal{F}$ is called a hereditary class if every graph isomorphic
to an induced subgraph of a graph in $\mathcal{F}$ belongs to $\mathcal{F}$.
We also restrict the intermediate steps to belong to hereditary graph classes
and study them.

######  Definition 1.3 (Generalized Brussels sprout).

Given a hereditary class $\mathcal{F}$, we define the game $n$-Brussels sprout
for $\mathcal{F}$ with parameters $(t_{1},t_{2},\cdots,t_{n})$, denoting it as
$BS_{n}(\mathcal{F}:t_{1},t_{2},t_{3},\dots,t_{n})$, as follows. The game
$BS_{n}(\mathcal{F}:t_{1},t_{2},t_{3},\dots,t_{n})$ starts with $n$ spots,
having $t_{1},t_{2},\cdots,t_{n}$ open tips, respectively. A valid move
consists of joining two open tips with a curve followed by drawing a crossbar
on the curve to create two new open tips. The graph obtained by considering
the spots and intersections of a curve and a crossbar as vertices, and the
curves joining two such vertices as edges, must remain inside the family
$\mathcal{F}$ at all times. The first player unable to provide a valid move,
loses.

###  1.2 Our contribution and organization of the article

  * •

In Section 2, we study the possible number of moves and winning strategies for
$n$-Brussels sprout for the families of forests, and graphs on orientable and
non-orientable surfaces of genus $k\geq 0$. We notice that the player who has
a winning strategy does not change even if we increase the value of the genus
for the orientable surfaces. This phenomenon is also noticed experimentally
for the game Sprout, however, probably our theoretical proof for Brussels
Sprout provides an explanation for the same.

  * •

In Section 3, we focus on studying the generalized Brussels sprout game for
the hereditary families of sparse planar graphs. In particular, we study the
game for the family $\mathcal{P}_{g}$ of planar graphs having girth at least
$g$. One particular case, when $g=4$, attracts our attention and we study it
in a deep way as usual.

  * •

In Section 4, we introduce a new, related game called Circular sprout. We
explore a relation between a particular class of Circular sprout and
$BS_{2}(\mathcal{P}_{4}:p,q)$, where $\mathcal{P}_{4}$ is the planar graph
with girth $g\geq 4$.

  * •

In Section 5, we present a full nimber characterization of the game Circular
sprout $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$. The proof is novel and uses the
method of structural induction.

  * •

In Section 6, we show that the nimber of $BS_{4}(\mathcal{P}_{4}:p,q)$ is
always $0$ implies that the second player always has a winning strategy using
the result from the section 5.

  * •

In Section 7, we conclude the article with discussions of several open
questions.

######  Note 1.4.

We will follow standard graph notation according to West [18] throughout this
article unless otherwise stated.

######  Note 1.5.

A preliminary version of this work accepted for presentation at ICGT 2022.

Figure 2: An example of a Brussels Sprout game.

##  2 Forests and graphs on surfaces

To begin the study, let us first consider the family of forests.

######  Theorem 2.1.

Let $\mathcal{F}_{t}$ be the family of forests. Then
$BS_{n}(\mathcal{F}_{t}:t_{1},t_{2},...,t_{n}$) ends after exactly $n-1$
moves.

###### Proof.

Since $\mathcal{F}_{t}$ is the family of forests, the resultant graph of
terminated $BS_{n}(\mathcal{F}:t_{1},t_{2},...,t_{n}$) must be a tree. That
is, it is possible to make a move until we create a tree. On the other hand,
once we create a tree through our game, it is not possible to make any other
move, as it will create a cycle.

Suppose that the game is terminated after $x$ moves and that $G$ is the
resultant graph. Therefore, $|V(G)|=(n+x)$ as we started with $n$ vertices and
in each move we have added exactly one vertex. Also, $|E(G)|=2x$ as we started
with no edges and in each move we have added exactly two edges. We know that
$G$ is a tree, and therefore, $|E(G)|=|V(G)|-1$. Hence we have $2x=(n+x)-1$,
which implies, $x=n-1$. ∎

Next, we will move our attention to the family $\mathcal{O}_{k}$ of graphs
that can be drawn on orientable surfaces of genus $k$ without crossing.

######  Theorem 2.2.

Let $\mathcal{O}_{k}$ be the family of graphs that can be drawn on orientable
surfaces of genus $k$ without crossing. Then the only possible numbers of
moves until the game $BS_{n}(\mathcal{O}_{k}:t_{1},t_{2},...,t_{n})$
terminates are

$(n-2)+2j+\sum_{i=1}^{n}t_{i},$

where $j=0,1,\cdots,k$.

###### Proof.

Suppose the game ends after $x$ moves and let the resultant graph after the
end of the game be $G$. Thus, $|V(G)|=n+x$ and $|E(G)|=2x$ as we start with
$n$ vertices, $0$ edges, and include exactly one vertex and two edges in each
move.

Furthermore, we observe that the game cannot end if a particular face contains
two or more open tips, while in the last move involved in creating a
particular face of $G$ will ensure at least one open tip inside the face.
Thus, the number of open tips is equal to the number of faces of $G$.
Moreover, in each move we close exactly two open tips, and create exactly two
open tips. Thus, the number of open tips remain invariant throughout the game.
Therefore, the number of faces in $G$ is equal to
$|F(G)|=\sum_{i=1}^{n}t_{i}$.

Notice that, even though $G$ is embedded on $\mathcal{O}_{k}$, it may be
possible to embed it on an orientable surface of genus less than $k$. Let $j$
be the least number for which $G$ can be embedded on $\mathcal{O}_{j}$. Thus,
$G$ will satisfy the Euler’s formula

$|V(G)|-|E(G)|+|F(G)|=2-2j$

for orientable surfaces.

Thus, by replacing the values of $|V(G)|$, $|E(G)|$ and $|F(G)|$ we get

$x+n-2x+\sum_{i=1}^{n}t_{i}=2-2j\implies x=(n-2)+2j+\sum_{i=1}^{n}t_{i}$

which completes the proof. ∎

Recall that the orientable surface with genus $0$ is nothing but the sphere,
and thus, the family $\mathcal{O}_{0}$ of graphs are nothing but planar
graphs. The above theorem characterizes all possible number of moves for the
game $BS_{n}(\mathcal{O}_{k}:t_{1},t_{2},\cdots,t_{n})$ to end. Clearly, when
$k=0$, that is, for the game
$BS_{n}(\mathcal{O}_{0}:t_{1},t_{2},\cdots,t_{n})$ the game will end after
exactly $(n-2)+\sum_{i=1}^{n}t_{i}$ moves. Therefore, for planar graphs, the
game will end after a constant number of moves, and the first player will win
if and only if that constant is odd irrespective of how the game gets played.

######  Corollary 2.3.

The game $BS_{n}(\mathcal{O}_{0}:t_{1},t_{2},\cdots,t_{n})$ will end exactly
after $(n-2)+\sum_{i=1}^{n}t_{i}$ moves and the first player will win if and
only if $n+\sum_{i=1}^{n}t_{i}$ is odd.

###### Proof.

Follows directly from Theorem 2.2 by restricting it for $k=0$. ∎

On the other hand, if we consider the game
$BS_{n}(\mathcal{O}_{k}:t_{1},t_{2},\cdots,t_{n})$ for all $k\geq 1$, even
though the number of moves after which the game may end is not a constant,
note that it only differs by an even number. Thus we have the following.

######  Corollary 2.4.

In the game $BS_{n}(\mathcal{O}_{k}:t_{1},t_{2},\cdots,t_{n})$ for $k\geq 1$,
the first player will win if and only if $n+\sum_{i=1}^{n}t_{i}$ is odd.

###### Proof.

Follows directly from Theorem 2.2 by observing that
$(n-2)+2j+\sum_{i=1}^{n}t_{i}$ is odd if and only if $n+\sum_{i=1}^{n}t_{i}$
is odd for all $j=0,1,\cdots,k$. ∎

On a similar vein, we also study the family $\mathcal{N}_{k}$ of graphs that
can be drawn on non-orientable surfaces of genus $k$ without crossing.

######  Theorem 2.5.

Let $\mathcal{N}_{k}$ be the family of graphs that can be drawn on non-
orientable surfaces of genus $k$ without crossing. Then the only possible
numbers of moves until the game
$BS_{n}(\mathcal{N}_{k}:t_{1},t_{2},...,t_{n})$ terminates are

$(n-2)+j+\sum_{i=1}^{n}t_{i},$

where $j=0,1,\cdots,k$.

###### Proof.

Suppose the game ends after $x$ moves and let the resultant graph after the
end of the game be $G$. Thus, we can observe that $G$ has $|V(G)|=n+x$,
$|E(G)|=2x$ and $|F(G)|=\sum_{i=1}^{n}t_{i}$ using the same arguments as in
the proof of Theorem 2.2.

Notice that, even though $G$ is embedded on $\mathcal{N}_{k}$, it may be
possible to embed it on a non-orientable surface of genus less than $k$. Let
$j$ be the least number for which $G$ can be embedded on $\mathcal{N}_{j}$.
Therefore, $G$ satisfies the Euler’s formula is

$|V(G)|-|E(G)|+|F(G)|=2-j.$

Thus, by replacing the values of $|V(G)|$, $|E(G)|$ and $|F(G)|$ we get

$x+n-2x+\sum_{i=1}^{n}t_{i}=2-j\implies x=(n-2)+j+\sum_{i=1}^{n}t_{i}$

which completes the proof. ∎

Recall that the non-orientable surface with genus $0$ is nothing but the
projective plane, and thus, the family $\mathcal{N}_{0}$ of graphs are nothing
but the projective planar graphs. Therefore the following corollary follows
directly.

######  Corollary 2.6.

The game $BS_{n}(\mathcal{N}_{0}:t_{1},t_{2},\cdots,t_{n})$ will end exactly
after $(n-2)+\sum_{i=1}^{n}t_{i}$ moves and the first player will win if and
only if $n+\sum_{i=1}^{n}t_{i}$ is odd.

###### Proof.

Follows directly from Theorem 2.5 by restricting it for $k=0$. ∎

However, in this case, for higher genus, unlike in the case of orientable
surfaces, the parity of the number of moves after which the game may end is
not the same. Therefore, depending on how the game is played, it may be won by
Player 1 or Player 2. Thus, it makes sense to analyse winning strategies. We
pose this as an open question.

######  Question 2.7.

Which player has a winning strategy for the game
$BS_{n}(\mathcal{N}_{k}:t_{1},t_{2},\cdots,t_{n})$ when $k\geq 1$?

##  3 Sparse planar graphs

In this section, let us focus on the family $\mathcal{P}_{g}$ of planar graphs
with girth at least $g$. The first result shows that if we fix a particular
value of $n$, then the number of moves after which the game
$BS_{n}(\mathcal{P}_{g}:t_{1},t_{2},...,t_{n})$ ends is a constant for large
enough values of $g$.

######  Theorem 3.1.

Let $\mathcal{P}_{g}$ be the family of planar graphs having girth at least
$g$. Then the game $BS_{n}(\mathcal{P}_{g}:t_{1},t_{2},\cdots,t_{n}$) game
ends exactly after $n-1$ moves for all $g\geq 2n+1$.

###### Proof.

Let $G_{x}$ be the resultant graph after $x$ number of moves. As we start with
$n$ vertices and add one vertex in each move, we have $|V(G_{x})|=(n+x)$.
Also, we start with zero edges and add two edges in each move. Thus we have
$|E(G_{x})|=2x$.

Thus after $n$ moves, we have $2n$ vertices and $2n$ edges in $G_{n}$. This
graph must have a cycle, and as the graph has only $2n$ vertices, the cycle
cannot have length greater than or equal to $2n+1$. This is a contradiction.

Hence, the number of moves cannot be more than $n-1$. On the other hand, $n-1$
moves are also the minimum number of moves due to Theorem 2.1. ∎

Next, we focus particularly on the family of triangle-free planar graphs, that
is, $\mathcal{P}_{4}$. We find upper and lower bounds of the number of moves
after which the game $BS_{n}(\mathcal{P}_{4}:t_{1},t_{2},...,t_{n})$ ends.

######  Theorem 3.2.

The number of moves after which the game
$BS_{n}(\mathcal{P}_{4}:t_{1},t_{2},...,t_{n})$ ends is between $(4+n)$ and
$(n-2)+\sum_{i=1}^{n}t_{i}$, where $n\geq 2$ and $t_{i}\geq 3$.

###### Proof.

Suppose the game ends after $x$ moves and let the resultant graph after the
end of the game be $G$ which is a planar graph, in particular. Thus, due to
Corollary 2.3 we have $x\leq(n-2)+\sum_{i=1}^{n}t_{i}$.

As we start with $n$ vertices and add one vertex in each move, we have
$|V(G_{x})|=(n+x)$. Also, as we start with zero edges and add two edges in
each move, we have $|E(G_{x})|=2x$. Furthermore, since $t_{i}\geq 3$ and
$n\geq 2$, we are forced to have $|F(G)|\geq 6$ which can be observed through
a brute force case analysis that we omit.

Hence by Euler’s Formula, we have

$\displaystyle|V(G)|-|E(G)|+|F(G)|=2$ $\displaystyle\implies(x+n)-2x+6\leq 2$
$\displaystyle\implies x\geq 4+n$

Therefore, $(4+n)\leq x\leq(n-2)+\sum_{i=1}^{n}t_{i}$. ∎

A natural question we can ask here is whether there is a play of
$BS_{n}(\mathcal{P}_{4}:t_{1},t_{2},...,t_{n})$ that ends after
$(n-2)+\sum_{i=1}^{n}t_{i}$ moves and one that ends after $(4+n)$ moves. In
the next result, we will see that indeed for $n=2$, such plays exist when the
ratio of $p$ and $q$ is at most two.

######  Theorem 3.3.

There exists plays of $BS_{2}(\mathcal{P}_{4}:p,q)$ which ends after $(p+q)$
and $6$ moves, respectively, for $p\leq q\leq 2p$.

###### Proof.

Let the two vertices present in the initial stage of the game
$BS_{2}(\mathcal{P}_{4}:p,q)$ be $x$ and $y$ positioned on a horizontal line,
$x$ being on the left side of $y$. Furthermore, let $x_{1},x_{2},...,x_{p}$ be
the open tips coming out of $x$, arranged in a clockwise order around $x$ and
let $y_{1},y_{2},...,y_{q}$ be the open tips coming out of $y$, arranged in an
anti-clockwise order around $y$.

First, we are going to describe the play of $BS_{2}(\mathcal{P}_{4}:p,q)$
which ends after $(p+q)$ moves for $q=(p+r)$ where $0\leq r\leq p$. Observe
that it is enough to describe the required sequences of the $(p+q)$ moves in
the play.

Let the first move be connecting $x_{1}$ to $y_{1}$ with a curve and putting
the crossbar $t_{1}$ on it. In the subsequent moves, we connect $x_{i}$ to
$y_{2i-1}$ with a curve and put the crossbar $t_{i}$ on it for
$i=2,3,\cdots,r+1$. After that we connect $x_{j}$ to $y_{r+j}$ with a curve
and put the crossbar $t_{j}$ for $j=r+2,r+3,\cdots,p$. That means, we have
made a total of $p$ moves till now.

Next, we connect $t_{i}$ to $t_{i+1}$ with a curve and put a crossbar $s_{i}$
on it for $i=1,2,\cdots,p-1$, which are $(p-1)$ more moves. Then we connect
$s_{i}$ with $y_{2i}$ with a curve and put a crossbar on it for
$i=1,2,\cdots,r$, which amounts to $r$ moves. Finally, we connect $t_{1}$ with
$t_{p}$ with a curve and put a crossbar on it. Observe that, this ends the
play as no more moves can be made and a total of $p+(p-1)+r+1=2p+r=p+q$ moves
are made. Thus we are done with the first part of the proof.

Secondly, we are going to describe the play of $BS_{2}(\mathcal{P}_{4}:p,q)$
which ends after $6$ moves. Observe that it is enough to describe the required
sequences of the $6$ moves in the play.

The first two moves in this case are connecting $x_{1}$ to $y_{1}$ and $x_{2}$
to $y_{2}$ with two curves and putting the crossbars $t_{1}$ and $t_{2}$ on
them, respectively. Notice that the above two curves divide the plane into two
regions: $R_{1}$ containing the open tip $x_{3}$, $R_{2}$ not containing it.
We connect $t_{1}$ and $t_{2}$ with a curve through $R_{1}$ and put a crossbar
$t_{3}$ on it. Next, we connect $x_{p}$ and $y_{3}$ to $t_{3}$ two curves and
put crossbars on them. Finally, connect $t_{1}$ and $t_{2}$ with a curve
through $R_{2}$ and put a crossbar on it. Observe that, this ends the play as
no more moves can be made and a total of $6$ moves are made. Thus, we are done
with the second part of the proof as well. ∎

$x_{1}$$x_{i}$$x_{2}$$x_{3}$$x_{p}$$x_{i-1}$$x_{i+1}$$y_{1}$$y_{j}$$y_{2}$$y_{3}$$y_{q}$$y_{j-1}$$y_{j+1}$

$=$$x_{1}$$x_{i}$$x_{2}$$x_{3}$$x_{i+1}$$y_{1}$$y_{j}$$y_{2}$$y_{j-1}$$y_{3}$

$x_{1}$$x_{i}$$x_{p}$$x_{p-1}$$x_{i-1}$$y_{1}$$y_{j}$$y_{q}$$y_{q-1}$$y_{j+1}$

Figure 3: Expressing a partially played Brussels sprout game as a sum of two
Circular sprout games.

From the above theorem, we can notice that the game
$BS_{2}(\mathcal{P}_{4}:p,q)$ does not have a clear winner, and depending on
the play, either Player 1 or Player 2 can win. Therefore, studying which
player has a winning strategy makes sense. However, when we tried to do it by
hand, it became extremely difficult, even for small values of $p$ and $q$.
Thus, a natural question to ask in this context is the following.

######  Question 3.4.

Which player has a winning strategy for the game $BS_{2}(\mathcal{P}_{4}:p,q)$
for all $p,q\geq 3$?

Keeping in mind, that our main goal of this article is to develop the theory
around Sprout’s conjecture (that is, Conjecture [15], we will, in fact,
consider an even more difficult problem and solve it to get a conclusive
answer to Question 3.4 as a direct corollary in the upcoming sections. The
above mentioned stronger result requires introducing a new game called the
Circular sprout and involves the notion of “nimber” [1].

##  4 The Circular sprout game and its relation with
$BS_{2}(\mathcal{P}_{4}:p,q)$

While studying the game $BS_{2}(\mathcal{P}_{4}:p,q)$, we encountered another
similar game which we found to be interesting. Let us define this new game
independently, and in a generalized form, even though in this article we will
study only a specific restriction of it which will help us in studying
$BS_{2}(\mathcal{P}_{4}:p,q)$.

This new game, named the $n$-Circular sprout game for the family $\mathcal{F}$
with parameters $(t_{1},t_{2},\cdots,t_{n})$, is denoted by the notation
$CS_{n}(\mathcal{F}:t_{1},t_{2},\cdots,t_{n})$. The initial set up of this
game consists of $n$ dots $v_{1},v_{2},\cdots,v_{n}$ arranged in a clockwise
order on the perimeter of a circle with $v_{i}$ having $t_{i}$ open tips
coming out in the interior of the circle. The rest of the rules of the game
are the same as Brussels sprout with the following added constraint: the
curves drawn by the players must be entirely contained in the interior of the
circle.

Next let us observe how this game is related to $BS_{2}(\mathcal{P}_{4}:p,q)$.
Let the open tips around the first spot be $x_{1},x_{2},\cdots,x_{p}$ arranged
in a clockwise order, and let the open tips around the second spot be
$y_{1},y_{2},\cdots,y_{q}$ arranged in an anti-clockwise order. Observe that,
the very first move by Player 1 in the game $BS_{2}(\mathcal{P}_{4}:p,q)$ is
unique up to renaming of the open tips. Therefore, without loss of generality
one can assume that the very first move is joining the open tip $x_{1}$ with
the open tip $y_{1}$ with a curve and then placing a crossbar on it. After
that, the second player is forced to join an open tip $x_{i}$ to an open tip
$y_{j}$, for some $i,j\neq 1$. This move will enable us to write the present
game as the sum of two Circular sprout game:
$CS_{4}(\mathcal{P}_{4}:i-2,1,j-2,1)$ and
$CS_{4}(\mathcal{P}_{4}:p-i,1,q-j,1)$ for some $i\in\\{2,3,\cdots,p\\}$ and
$j\in\\{2,3,\cdots,q\\}$. Hence it will be enough to study and understand the
games of the type $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ (see Figure 3 for
reference).

###  4.1 Nimber

Before moving forward with the study of these games, we would like to point
out that all the games discussed here are two player finite impartial games,
and thus their nimber [17] can be calculated [17]. To conclude which player
has a winning strategy for a particular two player impartial game, it is
enough to calculate the nimber value of the game; the second player has an
winning strategy if and only if the nimber of a game is $0$ [1].

Recall that, to calculate the nimber of a game $X$, one first need to generate
the entire game tree having $X$ as its root. Next, the leaves of the tree are
all assigned nimber equal to $0$, while for the other nodes, its nimber is the
least non-negative integer which does not occur as a nimber of any of its
children. Let us denote the nimber of a game $X$ by $\eta[X]$ for convenience.
We know that if an impartial game $X$ can be written as a sum of two impartial
games, $Y$ and $Z$, then the nimber of $X$ can be given by
$\eta[X]=\eta[Y]\oplus\eta[Z]$, where $\oplus$ denote the XOR operation [1].

Thus our objective now is to calculate nimber of the game
$CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ for $p,q\geq 0$. Note that, the games
$CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ and $CS_{4}(\mathcal{P}_{4}:q,1,p,1)$ are
the exact same games up to symmetry. Thus it is enough to calculate
$\eta[CS_{4}(\mathcal{P}_{4}:p,1,q,1)]$ for all $q\geq p\geq 0$.

##  5 Nimber of $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$

We assume $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ to be embedded as $p$ on the left,
$q$ on the right and the singular open tips to be at the top and bottom.

######  Theorem 5.1.

For all $0\leq p\leq q$, we have

$\eta[CS_{4}(\mathcal{P}_{4}:p,1,q,1)]=\begin{cases}1&\text{if $p=q$},\\\
\frac{4}{5}(p+q-i)+2\lfloor\frac{i}{4}\rfloor&\text{if
$p<q<2p-\lfloor\frac{|p-2|}{2}\rfloor$ where $i\equiv p+q(mod\ 5)$}\\\
2p&\text{if $q\geq 2p-\lfloor\frac{|p-2|}{2}\rfloor$.}\end{cases}$

where $1,2,3,4,5$ are the representative of the integers modulo $5$.

###  5.1 Proof of Theorem 5.1

The proof of Theorem 5.1 uses the method of structural induction and is
lengthy and complicated. For the benefit of the reader, we will divide the
proof into several lemmas and observations, and also present it across
different subsections.

####  5.1.1 The basic set up for the proof

Let us assume a typical pictorial representation of the game
$CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ to be as follows. Let the reference circle
of the game be the circle having unit radius and $(0,0)$ as its centre. After
that, let the four spots on it, along with their positions, be $x$ at
$(-1,0)$, $t$ at $(0,1)$, $y$ at $(1,0)$ and $b$ at $(0,-1)$. Furthermore, let
$x_{1},x_{2},...,x_{p}$ be the open tips coming out of $x$, arranged in a
clockwise order around $x$ and let $y_{1},y_{2},...,y_{q}$ be the open tips
coming out of $y$, arranged in an anti-clockwise order around $y$. Also let
$t_{1}$ and $b_{1}$ be the open tips coming out of $t$ and $b$, respectively.

Notice that, there can be two types of moves that the first player can perform
on the given initial stage of the game $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$. The
first type is to connect $t_{1}$ with $b_{1}$ with a curve and then put a
crossbar on it. However, this creates a game equivalent to the sum of the two
games $CS_{4}(\mathcal{P}_{4}:p,0,1,0)$ and $CS_{4}(\mathcal{P}_{4}:1,0,q,0)$.
The second type of move is to join $x_{p^{\prime}+1}$ with $y_{q^{\prime}+1}$
with a curve and then put a crossbar on it. This creates a game equivalent to
the sum of the two games $CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q^{\prime},1)$
and $CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,q^{\prime\prime},1)$, where
$p^{\prime}\in\\{0,1,\cdots,p^{\prime}-1\\}$,
$q^{\prime}\in\\{0,1,\cdots,q^{\prime}-1\\}$,
$p^{\prime\prime}=p-p^{\prime}-1$ and $q^{\prime\prime}=q-q^{\prime}-1$. From
now on, we will assume $p^{\prime}\in\\{0,1,\cdots,p^{\prime}-1\\}$,
$q^{\prime}\in\\{0,1,\cdots,q^{\prime}-1\\}$,
$p^{\prime\prime}=p-p^{\prime}-1$ and $q^{\prime\prime}=q-q^{\prime}-1$ as
general convention for this proof.

Observe that, irrespective of the moves, the game becomes a sum of similar
kinds of games allowing us to use induction. That is why, we will use the
method of strong induction on $p$ to prove this result.

####  5.1.2 Base case

Before going to the base case, let us first prove some useful lemmas.

######  Lemma 5.2.

We have

  1. (i)

$\eta[CS_{4}(\mathcal{P}_{4}:0,0,q,0)]=0$ for all $q\geq 0$,

  2. (ii)

$\eta[CS_{4}(\mathcal{P}_{4}:0,1,0,1)]=1$,

  3. (iii)

$\eta[CS_{4}(\mathcal{P}_{4}:1,0,q,0)]=1$ for all $q\geq 1$,

  4. (iv)

$\eta[CS_{4}(\mathcal{P}_{4}:0,1,q,1)]=0$ for all $q\geq 1$.

###### Proof.

(i) Notice that the game $CS_{4}(\mathcal{P}_{4}:0,0,q,0)$ does not have any
move, and thus trivially,

$\eta[CS_{4}(\mathcal{P}_{4}:0,0,q,0)]=0.$ (1)

(ii) Observe that the game $CS_{4}(\mathcal{P}_{4}:0,1,0,1)$ has exactly one
move, that is, connecting $t_{1}$ and $b_{1}$ with a curve, and this move
leaves the game in a position where no further moves are possible. Thus,

$\eta[CS_{4}(\mathcal{P}_{4}:0,1,0,1)]=1.$ (2)

(iii) Note that the only possible move in the game
$CS_{4}(\mathcal{P}_{4}:1,0,q,0)$ is to connect $x_{1}$ to some
$y_{q^{\prime}+1}$ after which the game will end. Therefore,

$\eta[CS_{4}(\mathcal{P}_{4}:1,0,q,0)]=1.$ (3)

(iv) In the game $CS_{4}(\mathcal{P}_{4}:0,1,q,1)$ for $q\geq 1$, the only
possible first move is to connect $t_{1}$ with $b_{1}$ by a curve. This can be
expressed as a sum of the games $CS_{4}(\mathcal{P}_{4}:0,0,1,0)$ and
$CS_{4}(\mathcal{P}_{4}:1,0,q,0)$. We already know that
$\eta[CS_{4}(\mathcal{P}_{4}:0,0,q,0)]=0$ by equation (1), and
$\eta[CS_{4}(\mathcal{P}_{4}:1,0,q,0)]=1$ due to equation 3. Hence the only
child of the game $CS_{4}(\mathcal{P}_{4}:0,1,q,1)$ has nimber

$\eta[CS_{4}(\mathcal{P}_{4}:0,0,q,0)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:1,0,q,0)]=1$
(4)

which implies

$\eta[CS_{4}(\mathcal{P}_{4}:0,1,q,1)]=0.$ (5)

This completes the proof. ∎

This implies that the formula given in the statement of Theorem 5.1 holds when
$p=0$.

######  Lemma 5.3.

We have

$\eta[CS_{4}(\mathcal{P}_{4}:1,1,q,1)]=\begin{cases}1&\text{ if }q=1,\\\
2&\text{ if }q\geq 2.\end{cases}$ (6)

###### Proof.

The game $CS_{4}(\mathcal{P}_{4}:1,1,q,1)$ has two types of children in the
game tree. The first, obtained by connecting $t_{1}$ and $b_{1}$ with a curve,
can be expressed as the sum of $CS_{4}(\mathcal{P}_{4}:1,0,1,0)$ and
$CS_{4}(\mathcal{P}_{4}:1,0,q,0)$. This game has nimber

$\eta[CS_{4}(\mathcal{P}_{4}:1,0,1,0)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:1,0,q,0)]=1\oplus
1=0$ (7)

due to equation (2) and (3). The second child is obtained by connecting
$x_{1}$ and $y_{q^{\prime}+1}$, and thus can be expressed as a sum of
$CS_{4}(\mathcal{P}_{4}:0,1,q^{\prime},1)$ and
$CS_{4}(\mathcal{P}_{4}:0,1,q^{\prime\prime},1)$, and thus has nimber

$\eta[CS_{4}(\mathcal{P}_{4}:0,1,q^{\prime},1)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:0,1,q^{\prime\prime},1)]=0\oplus
0=0$ (8)

for $q^{\prime},q^{\prime\prime}\geq 1$ due to equation (5). On the other
hand, using equation (2) and (5), when $q^{\prime}=0$ (or
$q^{\prime\prime}=0$) we have

$\eta[CS_{4}(\mathcal{P}_{4}:0,1,0,1)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:0,1,q-1,1)]=1\oplus
0=1$ (9)

for $q\geq 2$. Notice that, if $q=1$, then

$\eta[CS_{4}(\mathcal{P}_{4}:0,1,0,1)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:0,1,0,1)]=1\oplus
1=0.$ (10)

That means, the game $CS_{4}(\mathcal{P}_{4}:1,1,q,1)$ has children with
nimber $0$ and $1$ when $q\geq 2$. On the other hand, if $q=1$, it has only
children with nimber $0$. Therefore, we have

$\eta[CS_{4}(\mathcal{P}_{4}:1,1,q,1)]=\begin{cases}1&\text{ if }q=1,\\\
2&\text{ if }q\geq 2.\end{cases}$ (11)

This completes the proof. ∎

Thus, the formula given in the statement is true for $p=1$ as well. Hence we
have verified the formula to be true for $p\leq 1$, and this is the base case
of our induction.

####  5.1.3 Induction hypothesis

Let us assume that the formula is true for all
$\eta[CS_{4}(\mathcal{P}_{4}:p-i,1,q,1)]$, where $i\in\\{1,2,\cdots,p\\}$. For
the induction step, we need to show that it is true for
$\eta[CS_{4}(\mathcal{P}_{4}:p,1,q,1)]$ as well.

####  5.1.4 Induction step: A key lemma

We will break our induction step of the proof across several lemmas. However,
before that we will make a general observation useful for all cases.

######  Lemma 5.4.

For all $0\leq p\leq q$,

$\eta[CS_{4}(\mathcal{P}_{4}:p,1,q,1)]\geq 1.$ (12)

###### Proof.

Notice that each of the games $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ has one child
which is expressed as a sum of $CS_{4}(\mathcal{P}_{4}:p,0,1,0)$ and
$CS_{4}(\mathcal{P}_{4}:1,0,q,0)$. By equation 3, this game has nimber

$\eta[CS_{4}(\mathcal{P}_{4}:p,0,1,0)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:1,0,q,0)]=1\oplus
1=0.$ (13)

Therefore, all the games of the type $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ has a
child with nimber $0$. This implies

$\eta[CS_{4}(\mathcal{P}_{4}:p,1,q,1)]\geq 1.$ (14)

Hence the proof. ∎

####  5.1.5 Induction step: When $p=q$.

Now we are ready to handle the case where $p=q$.

######  Lemma 5.5.

If $\eta[CS_{4}(\mathcal{P}_{4}:n,1,q,1)]$ satisfy the formula given in the
statement of Theorem 5.1 for all $n\leq p-1$, then
$\eta[CS_{4}(\mathcal{P}_{4}:p,1,p,1)]=1$.

###### Proof.

When $p=q$, note that because of Lemma 5.4 it is enough to show that none of
the children of $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ in the game tree has nimber
equal to $1$. That is, we need to show that

$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q^{\prime},1)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,q^{\prime\prime},1)]\neq
1.$

Notice that, by our induction hypothesis, both
$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q^{\prime},1)]$ and
$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,q^{\prime\prime},1)]$ has even
values unless $p^{\prime}=q^{\prime}$, and hence, as the XOR of two even
numbers is even, we are done unless $p^{\prime}=q^{\prime}$. If
$p^{\prime}=q^{\prime}$, then both
$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q^{\prime},1)]$ and
$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,q^{\prime\prime},1)]$ are
equal to $1$. Thus, in this case also,

$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,p^{\prime},1)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,p^{\prime\prime},1)]=1\oplus
1=0.$

This implies that

$\eta[CS_{4}(\mathcal{P}_{4}:p,1,p,1)]=1$

and concludes the proof. ∎

####  5.1.6 Induction step: When $q\geq 2p-\lfloor\frac{p-2}{2}\rfloor$.

######  Lemma 5.6.

If $\eta[CS_{4}(\mathcal{P}_{4}:n,1,q,1)]$ satisfies the formula given in the
statement of Theorem 5.1 for all $n\leq p-1$, then
$\eta[CS_{4}(\mathcal{P}_{4}:p,1,q,1)]=2p$ when $q\geq
2p-\lfloor\frac{p-2}{2}\rfloor$.

###### Proof.

When $q\geq 2p-\lfloor\frac{p-2}{2}\rfloor$, we need to show that none of the
children of $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ in the game tree has nimber
equal to $2p$, where as, for each $i\in\\{1,2,\cdots,2p-1\\}$, there exists a
child of $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ in the game tree which has nimber
equal to $i$.

First, we will show that the odd numbers less than $2p$ appear as the nimbers
of the children of $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ in the game tree. For
that, let us consider the children that can be expressed as sum of the games
$CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q^{\prime},1)$ and
$CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,q^{\prime\prime},1)$, where $q\geq
2p-\lfloor\frac{p-2}{2}\rfloor$ and $p^{\prime}=q^{\prime}$. In this scenario,
note that we have

$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q^{\prime},1)]=\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,p^{\prime},1)]=1$

by induction hypothesis. Moreover, observe that

$\displaystyle q^{\prime\prime}=q-1-q^{\prime}$
$\displaystyle\geq\left(2p-\lfloor\frac{p-2}{2}\rfloor\right)-1-p^{\prime}$
$\displaystyle\geq\left(2p-\lfloor\frac{p-2}{2}\rfloor-1-p^{\prime}\right)+(p^{\prime}-p^{\prime})+\left(\lfloor\frac{p^{\prime\prime}-2}{2}\rfloor-\lfloor\frac{p^{\prime\prime}-2}{2}\rfloor\right)+(1-1)$
$\displaystyle\geq\left(2(p-p^{\prime}-1)-\lfloor\frac{p^{\prime\prime}-2}{2}\rfloor\right)+\left(p^{\prime}+\lfloor\frac{p^{\prime\prime}-2}{2}\rfloor-\lfloor\frac{p-2}{2}\rfloor+1\right)$
$\displaystyle\geq
2p^{\prime\prime}-\lfloor\frac{p^{\prime\prime}-2}{2}\rfloor.$

This implies

$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,q^{\prime\prime},1)]=2p^{\prime\prime}$

due to the induction hypothesis. Therefore,

$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,p^{\prime},1)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,q^{\prime\prime},1)]=1\oplus
2p^{\prime\prime}=2p^{\prime\prime}+1$

is the nimber of a child of $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ in the game
tree. As $p^{\prime\prime}\in\\{0,1,\cdots,p-1\\}$, the above covers all odd
numbers less than $2p$.

Next, we will show that the even numbers less than $2p$ appear as the nimbers
of the children of $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ in the game tree. For
that, let us consider the children that can be expressed as the sum of the
games $CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q-1,1)$ and
$CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,0,1)$. In this scenario, note that
we have

$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,0,1)]=0$

by equation (5). Also

$\displaystyle q-1$ $\displaystyle\geq(2p-\lfloor\frac{p-2}{2}\rfloor)-1$
$\displaystyle\geq\left(2p-\lfloor\frac{p-2}{2}\rfloor-1\right)+(2p^{\prime}-2p^{\prime})+\left(\lfloor\frac{p^{\prime}-2}{2}\rfloor-\lfloor\frac{p^{\prime}-2}{2}\rfloor\right)$
$\displaystyle\geq(2p^{\prime}-\lfloor\frac{p^{\prime}-2}{2}\rfloor)+\left(2p-2p^{\prime}+\lfloor\frac{p^{\prime}-2}{2}\rfloor-\lfloor\frac{p-2}{2}\rfloor-1\right)$
$\displaystyle\geq 2p^{\prime}-\lfloor\frac{p^{\prime}-2}{2}\rfloor.$

This implies

$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q-1,1)]=2p^{\prime}$

due to the induction hypothesis. Therefore,

$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q-1,1)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,0,1)]=2p^{\prime}\oplus
0=2p^{\prime}$

is the nimber of a child of $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ in the game
tree. As $p^{\prime}\in\\{0,1,\cdots,p-1\\}$, the above covers all even
numbers less than $2p$.

Now let us show that there is no child of $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ in
the game tree whose nimber equals $2p$. Notice that, in general

$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q^{\prime},1)]\leq 2p^{\prime}$

due to the induction hypothesis. Therefore,

$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q^{\prime},1)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,q^{\prime\prime},1)]\leq
2p^{\prime}+2p^{\prime\prime}=2(p^{\prime}+p-p^{\prime}-1)<2p.$

Hence we are done. ∎

####  5.1.7 Induction step: When $p<q<2p-\lfloor\frac{p-2}{2}\rfloor$.

When $p<q<2p-\lfloor\frac{p-2}{2}\rfloor$, proving the induction step needs
careful treatment. Due to equation (14), we know that

$\eta[CS_{4}(\mathcal{P}_{4}:p,1,q,1)]\geq 1.$

Now to prove this case, first we need to show that

$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q^{\prime},1)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,q^{\prime\prime},1)]\neq\frac{4}{5}(p+q-i)+2\lfloor\frac{i}{4}\rfloor,$

where $i\equiv p+q(mod\ 5)$ and $1,2,3,4,5$ are the representative of the
integers modulo $5$.

######  Lemma 5.7.

If $\eta[CS_{4}(\mathcal{P}_{4}:n,1,q,1)]$ satisfies the formula given in the
statement of Theorem 5.1 for all $n\leq p-1$, then

$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q^{\prime},1)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,q^{\prime\prime},1)]\neq\frac{4}{5}(p+q-i)+2\lfloor\frac{i}{4}\rfloor,$

where $p<q<2p-\lfloor\frac{p-2}{2}\rfloor$, $i\equiv p+q(mod\ 5)$, and
$1,2,3,4,5$ are the representative of the integers modulo $5$.

###### Proof.

Without loss of generality, let us assume $q^{\prime}\geq p^{\prime}$. When
$p^{\prime}=q^{\prime}$, we have

$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q^{\prime},1)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,q^{\prime\prime},1)]\neq\frac{4}{5}(p+q-i)+2\lfloor\frac{i}{4}\rfloor$

as the left-hand side is of the form $1\oplus x$, where $x$ is an even number.
That is, the left-hand side is an odd number while the right-hand side is an
even number.

Next suppose that
$p^{\prime}<q^{\prime}<2p^{\prime}-\lfloor\frac{p^{\prime}-2}{2}\rfloor$ and
$p^{\prime\prime}<q^{\prime\prime}<2p^{\prime\prime}-\lfloor\frac{p^{\prime\prime}-2}{2}\rfloor$
(or
$q^{\prime\prime}<p^{\prime\prime}<2q^{\prime\prime}-\lfloor\frac{q^{\prime\prime}-2}{2}\rfloor$).
Moreover, let $i\equiv(p+q)\pmod{5}$,
$i^{\prime}\equiv(p^{\prime}+q^{\prime})\pmod{5}$, and
$i^{\prime\prime}\equiv(p^{\prime\prime}+q^{\prime\prime})\pmod{5}$. In this
scenario, $i^{\prime}$ and $i^{\prime\prime}$ can have some specific values
depending on $i$. If we know these values, then it is possible to compute and
compare the terms and show that

$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q^{\prime},1)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,q^{\prime\prime},1)]<\frac{4}{5}(p+q-i)+2\lfloor\frac{i}{4}\rfloor.$

We will demonstrate a sample calculation for one of the cases, and omit the
detailed calculations for the others. However, we will summarize them in a
consolidated manner in the comparison table (Table 1).

A sample calculation: If $i=4$, the possible values for
$\\{i^{\prime},i^{\prime\prime}\\}$ are $\\{5,2\\}$, $\\{1,1\\}$, and
$\\{3,4\\}$. When $\\{i^{\prime},i^{\prime\prime}\\}=\\{5,2\\}$ we have

$\displaystyle\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q^{\prime},1)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,q^{\prime\prime},1)]$
$\displaystyle=\frac{4}{5}(p+q-2-5-2)+2$ $\displaystyle=\frac{4}{5}(p+q+1)-6$
$\displaystyle\neq\frac{4}{5}(p+q+1)-2.$

$i$ | $\\{i^{\prime},i^{\prime\prime}\\}$ | $\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q^{\prime},1)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,q^{\prime\prime},1)]$ | $\frac{4}{5}(p+q-i)+2\lfloor\frac{i}{4}\rfloor$
---|---|---|---
| $\\{5,3\\}$ | $\frac{4}{5}(p+q)-6$ |
$5$ | $\\{1,2\\}$ | $\frac{4}{5}(p+q)-4$ | $\frac{4}{5}(p+q)-2$
| $\\{4,4\\}$ | $\frac{4}{5}(p+q)-4$ |
| $\\{5,2\\}$ | $\frac{4}{5}(p+q+1)-6$ |
$4$ | $\\{1,1\\}$ | $\frac{4}{5}(p+q+1)-4$ | $\frac{4}{5}(p+q+1)-2$
| $\\{3,4\\}$ | $\frac{4}{5}(p+q+1)-6$ |
| $\\{5,1\\}$ | $\frac{4}{5}(p+q+2)-6$ |
$3$ | $\\{2,4\\}$ | $\frac{4}{5}(p+q+2)-6$ | $\frac{4}{5}(p+q+2)-4$
| $\\{3,3\\}$ | $\frac{4}{5}(p+q+2)-8$ |
| $\\{5,5\\}$ | $\frac{4}{5}(p+q+3)-8$ |
$2$ | $\\{4,1\\}$ | $\frac{4}{5}(p+q+3)-6$ | $\frac{4}{5}(p+q+3)-4$
| $\\{3,2\\}$ | $\frac{4}{5}(p+q+3)-8$ |
| $\\{5,4\\}$ | $\frac{4}{5}(p+q+4)-8$ |
$1$ | $\\{3,1\\}$ | $\frac{4}{5}(p+q+4)-8$ | $\frac{4}{5}(p+q+4)-4$
| $\\{2,2\\}$ | $\frac{4}{5}(p+q+4)-8$ |
Table 1: The comparison table.

When $q^{\prime}\geq 2p^{\prime}-|\lfloor\frac{p^{\prime}-2}{2}\rfloor|$, then
note that

$\begin{split}q^{\prime\prime}=q-q^{\prime}-1&\leq
q-2p^{\prime}+|\lfloor\frac{p^{\prime}-2}{2}\rfloor|-1\\\ &\leq
q-2p^{\prime}+\frac{p^{\prime}}{2}-2\\\ &\leq q-1.5(p-p^{\prime\prime}-1)-2\\\
&\leq(q-1.5p)+1.5p^{\prime\prime}-0.5\\\ &<1.5p^{\prime\prime}-1\\\ &\leq
2p^{\prime\prime}-\lfloor\frac{p^{\prime\prime}-2}{2}\rfloor.\end{split}$ (15)

The above inequalities follow if we have $p^{\prime}\geq 2$. Otherwise also,
for the specific case of $p^{\prime}=0$ or $1$, one can still prove
$q^{\prime\prime}\leq
2p^{\prime\prime}-\lfloor\frac{|p^{\prime\prime}-2|}{2}\rfloor$ directly.

Thus, if $p^{\prime\prime}+q^{\prime\prime}\equiv i^{\prime\prime}\pmod{5}$,
we must have

$\displaystyle\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q^{\prime},1)]$
$\displaystyle\oplus\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,q^{\prime\prime},1)]$
$\displaystyle\leq
2p^{\prime}+\frac{4}{5}(p^{\prime\prime}+q^{\prime\prime}-i^{\prime\prime})+2\lfloor\frac{i^{\prime\prime}}{4}\rfloor$
$\displaystyle=2p^{\prime}+\frac{4}{5}((p-p^{\prime}-1)+(q-q^{\prime}-1)-i^{\prime\prime})+2\lfloor\frac{i^{\prime\prime}}{4}\rfloor$
$\displaystyle=2p^{\prime}+\frac{4}{5}(p+q)-\frac{4}{5}((p^{\prime}+q^{\prime})+2+i^{\prime\prime})+2\lfloor\frac{i^{\prime\prime}}{4}\rfloor$
$\displaystyle\leq
2p^{\prime}+\frac{4}{5}(p+q)-\frac{4}{5}((p^{\prime}+2p^{\prime}-\lfloor\frac{p^{\prime}-2}{2}\rfloor)+2+i^{\prime\prime})+2\lfloor\frac{i^{\prime\prime}}{4}\rfloor$
$\displaystyle\leq
2p^{\prime}+\frac{4}{5}(p+q)-\frac{4}{5}((p^{\prime}+2p^{\prime}-\frac{p^{\prime}}{2}+1)+2+i^{\prime\prime})+2\lfloor\frac{i^{\prime\prime}}{4}\rfloor$
$\displaystyle\leq\frac{4}{5}(p+q)-\frac{4}{5}(3+i^{\prime\prime})+2\lfloor\frac{i^{\prime\prime}}{4}\rfloor$
$\displaystyle<\frac{4}{5}(p+q-i)+2\lfloor\frac{i}{4}\rfloor$

where $p+q\equiv i\pmod{5}$. Note that, in the last step, strict inequality
holds irrespective of the values of $i$ and $i^{\prime\prime}$. Furthermore,
the above inequalities follow if we have $p^{\prime}\neq 1$. Otherwise also,
for the specific case of $p^{\prime}=1$, one can still prove that the left-
hand side of the inequality is less than the eventual right-hand side of the
inequality. ∎

Now it remains to show that for each
$x\in\\{1,2,\cdots,\frac{4}{5}(p+q-i)+2\lfloor\frac{i}{4}\rfloor\\}$ where
$(p+q)\equiv i\pmod{5}$ it is possible to find $p^{\prime}$ and $q^{\prime}$
such that

$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q^{\prime},1)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime\prime},1,q^{\prime\prime},1)]=x.$

######  Lemma 5.8.

Suppose that $\eta[CS_{4}(\mathcal{P}_{4}:n,1,q,1)]$ satisfies the formula
given in the statement of Theorem 5.1 for all $n\leq p-1$ where
$p<q<2p-\lfloor\frac{p-2}{2}\rfloor$. Then there exists a child of the game
$CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ in its game tree having nimber equal to $l$
where $l\in\\{1,3,\cdots,\frac{4}{5}(p+q-i)+2\lfloor\frac{i}{4}\rfloor-1\\}$
and $(p+q)\equiv i\pmod{5}$.

###### Proof.

Let $\frac{4}{5}(p+q-i)+2\lfloor\frac{i}{4}\rfloor=n_{1}$ and let
$\eta[CS_{4}(\mathcal{P}_{4}:p-1,1,q-1,1)]=n_{2}$. We will show that
$n_{2}\geq n_{1}-2$.

If $p-1<q-1<2(p-1)-\lfloor\frac{p-3}{2}\rfloor$, then, assuming $(p+q-2)\equiv
i_{2}\pmod{5}$, we have

$\displaystyle n_{2}-n_{1}$
$\displaystyle=\left(\frac{4}{5}(p-1+q-1-i_{2})+2\lfloor\frac{i_{2}}{4}\rfloor\right)-\left(\frac{4}{5}(p+q-i)+2\lfloor\frac{i}{4}\rfloor\right)$
$\displaystyle=\frac{4}{5}(i-i_{2}-2)+2\lfloor\frac{i_{2}}{4}\rfloor-2\lfloor\frac{i}{4}\rfloor.$

Notice that, $i=3,4,5$ implies $i_{2}=i-2$. Thus

$n_{2}-n_{1}=2\lfloor\frac{i_{2}}{4}\rfloor-2\lfloor\frac{i}{4}\rfloor\geq-2.$

If $i=1,2$, then $i_{2}=i+3$ which implies

$n_{2}-n_{1}=-4+2\lfloor\frac{i_{2}}{4}\rfloor-2\lfloor\frac{i}{4}\rfloor\geq-2.$

If $2(p-1)-\lfloor\frac{p-3}{2}\rfloor\leq
q-1<2p-\lfloor\frac{p-2}{2}\rfloor$, then as the maximum difference between
the lower and upper bound of $q-1$ is at most $1$, and as $q-1$ is an integer,
we can say that

$q=2(p-1)-\lfloor\frac{p-3}{2}\rfloor+1.$

Hence

$\displaystyle n_{2}-n_{1}$
$\displaystyle=2(p-1)-\frac{4}{5}(p+q-i)+2\lfloor\frac{i}{4}\rfloor$
$\displaystyle\geq
2p-2-\frac{4}{5}(p+2p-2-\lfloor\frac{p-3}{2}\rfloor+1-i)+2\lfloor\frac{i}{4}\rfloor$
$\displaystyle\geq
2p-2-\frac{4}{5}(3p-1-(\frac{p-3}{2})+0.5-i)+2\lfloor\frac{i}{4}\rfloor$
$\displaystyle=2p-2-\frac{4}{5}(\frac{5p}{2}+1-i)+2\lfloor\frac{i}{4}\rfloor$
$\displaystyle=-2-\frac{4}{5}(1-i)+2\lfloor\frac{i}{4}\rfloor$
$\displaystyle\geq-2.$

Therefore, $n_{2}\geq n_{1}-2$. That means, for each non-negative integer less
than $n_{2}$ the game $CS_{4}(\mathcal{P}_{4}:p-1,1,q-1,1)$ has a child having
nimber equal to it. In particular, for each non-negative odd integer less than
$n_{2}$, $CS_{4}(\mathcal{P}_{4}:p-1,1,q-1,1)$ has a child having nimber equal
to it.

Let $l\in\\{1,3,\cdots,n_{1}-3\\}$ be an odd integer. We know that,
$CS_{4}(\mathcal{P}_{4}:p-1,1,q-1,1)$ has a child with nimber $l$. However, we
also know that the child must be obtained by connecting $x_{a+1}$ and
$y_{a+1}$ with a curve, and its nimber is given by

$\eta[CS_{4}(\mathcal{P}_{4}:a,1,a,1)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:p-a-2,1,q-a-2,1)]=l.$

As $\eta[CS_{4}(\mathcal{P}_{4}:a,1,a,1)]=1$, we must have

$\eta[CS_{4}(\mathcal{P}_{4}:p-a-2,1,q-a-2,1)]=l-1.$

Thus the child of $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ obtained by connecting
$x_{a+2}$ and $y_{a+2}$ has nimber

$\eta[CS_{4}(\mathcal{P}_{4}:a+1,1,a+1,1)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:p-a-2,1,q-a-2,1)]=l.$

Moreover, the child of $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ obtained by
connecting $x_{1}$ and $y_{1}$ has nimber

$\eta[CS_{4}(\mathcal{P}_{4}:0,1,0,1)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:p-1,1,q-1,1)]=n_{1}-1.$

Thus, for each $l\in\\{1,3,\cdots,n_{1}-1\\}$ there exists a child of
$CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ having nimber equal to $l$. ∎

Last but not the least, we are going to show that the game
$CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ has a child with nimber $l$ for all even
positive integers $l$ less than
$\frac{4}{5}(p+q-i)+2\lfloor\frac{i}{4}\rfloor\\}$ where $(p+q)\equiv
i\pmod{5}$.

######  Lemma 5.9.

Suppose that $\eta[CS_{4}(\mathcal{P}_{4}:n,1,q,1)]$ satisfies the formula
given in the statement of Theorem 5.1 for all $n\leq p-1$ where
$p<q<2p-\lfloor\frac{|p-2|}{2}\rfloor$. Then there exists a child of the game
$CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ in its game tree having nimber equal to $l$
where $l\in\\{2,4,\cdots,\frac{4}{5}(p+q-i)+2\lfloor\frac{i}{4}\rfloor-2\\}$
and $(p+q)\equiv i\pmod{5}$.

###### Proof.

Let $\frac{4}{5}(p+q-i)+2\lfloor\frac{i}{4}\rfloor=n_{1}$. We want to show
that

$\eta[CS_{4}(\mathcal{P}_{4}:n,1,q,1)]=n_{1}.$

To do so, we will consider some cases. The first case is if

$(q+1)\geq 2(p-1)-\lfloor\frac{|(p-1)-2|}{2}\rfloor.$

This implies

$\displaystyle q-1$ $\displaystyle\geq
2(p-1)-\lfloor\frac{|(p-1)-2|}{2}\rfloor-2$ $\displaystyle\geq
2(p-3)-\lfloor\frac{|(p-3)-2|}{2}\rfloor.$

Additionally, if $p$ is even, then

$\displaystyle q-1$ $\displaystyle\geq
2(p-1)-\lfloor\frac{|(p-1)-2|}{2}\rfloor-2$ $\displaystyle\geq
2(p-2)-\lfloor\frac{|(p-2)-1|}{2}\rfloor.$

As we also know that

$q<2p-\lfloor\frac{|p-2|}{2}\rfloor.$

we have

$\displaystyle n_{1}$
$\displaystyle=\frac{4}{5}(p+q-i)+2\lfloor\frac{i}{4}\rfloor$
$\displaystyle<\frac{4}{5}(p+2p-\lfloor\frac{|p-2|}{2}\rfloor-i)+2\lfloor\frac{i}{4}\rfloor$
$\displaystyle\implies n_{1}$
$\displaystyle\leq\frac{4}{5}(3p-\frac{p}{2}+1.5-i)+2\lfloor\frac{i}{4}\rfloor-1$
$\displaystyle\leq 2p+\frac{4}{5}(1.5-i)+2\lfloor\frac{i}{4}\rfloor-1$
$\displaystyle\implies n_{1}$ $\displaystyle<2p$ $\displaystyle\implies n_{1}$
$\displaystyle\leq 2(p-1).$

In these cases, consider the child of $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ which
can be written as the sum of $CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q-1,1)$ and
$CS_{4}(\mathcal{P}_{4}:p-p^{\prime}-1,1,0,1)$ where $q-1\geq
2p^{\prime}-\lfloor\frac{|p^{\prime}-2|}{2}\rfloor$. Notice that

$\eta[CS_{4}(\mathcal{P}_{4}:p-p^{\prime}-1,1,0,1)]=0$

according to equation (5) and

$\eta[CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q-1,1)]=2p^{\prime}.$

Observe that, this will cover all the even numbers up to $2(p-3)$, and up to
$2(p-2)$ if $p$ is even.

Therefore, we only need to think about the case when $p$ is odd and
$n_{1}=2(p-1)$. In this case, $n_{1}$ is divisible by $4$. Consider the child
obtained by connecting $x_{p-1}$ with $y_{q-2}$. This will imply that
$CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ has a child having nimber

$\eta[CS_{4}(\mathcal{P}_{4}:p-2,1,q-3,1)]\oplus\eta[CS_{4}(\mathcal{P}_{4}:1,1,2,1)]=(n_{1}-4)\oplus
2=n_{1}-2.$

Thus we are done when $(q+1)\geq 2(p-1)-\lfloor\frac{|(p-1)-2|}{2}\rfloor$.

On the other hand, if $(q+1)<2(p-1)-\lfloor\frac{|(p-1)-2|}{2}\rfloor$, then
$p<q$ implies $p-1<q+1$, by induction hypothesis we have
$\eta[CS_{4}(\mathcal{P}_{4}:p-1,1,q+1,1)]=n_{1}$.

Thus, in particular, for each $l\in\\{2,4,\cdots,n_{1}-2\\}$, there exists a
child of $CS_{4}(\mathcal{P}_{4}:p-1,1,q+1,1)$ having nimber equal to $l$.
Observe that, this child must be a sum of two games of the form
$CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q^{\prime},1)$ and
$CS_{4}(\mathcal{P}_{4}:p-p^{\prime}-2,1,q-q^{\prime},1)$. Due to equation
(15), we know that one of these children will satisfy the conditions of the
second line of the formula given in Theorem 5.1.

Next consider the child of $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ obtained by
connecting $x_{p^{\prime}+1}$ and $y_{q^{\prime}+1}$ can be expressed as a sum
of the games $CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q^{\prime},1)$ and
$CS_{4}(\mathcal{P}_{4}:p-p^{\prime}-1,1,q-q^{\prime}-1,1)$. Due to equation
(15), we know that one of these children will satisfy the conditions of the
second line of the formula given in Theorem 5.1.

In fact as $p\neq q$, it is possible to assume without loss of generality that
both $CS_{4}(\mathcal{P}_{4}:p-p^{\prime}-2,1,q-q^{\prime},1)$ and
$CS_{4}(\mathcal{P}_{4}:p-p^{\prime}-1,1,q-q^{\prime}-1,1)$ satisfy the
conditions of the second line of the formula given in Theorem 5.1.

This implies

$\displaystyle\eta[CS_{4}(\mathcal{P}_{4}:p-p^{\prime}-2,1,q-q^{\prime},1)]$
$\displaystyle=\frac{4}{5}(p+q-p^{\prime}-q^{\prime}-2-i_{1})+2\lfloor\frac{i_{1}}{2}\rfloor$
$\displaystyle=\eta[CS_{4}(\mathcal{P}_{4}:p-p^{\prime}-1,1,q-q^{\prime}-1,1)].$

Thus, we can conclude that this game, expressed as a sum of
$CS_{4}(\mathcal{P}_{4}:p^{\prime},1,q^{\prime},1)$ and
$CS_{4}(\mathcal{P}_{4}:p-p^{\prime}-1,1,q-q^{\prime}-1,1)$, which is a child
of $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$, has nimber equal to $l$. ∎

####  5.1.8 Concluding the proof

Proof of Theorem 5.1. The proof follows from the induction method presented
above. ∎

##  6 Nimber and winning strategy for $BS_{2}(\mathcal{P}_{4}:p,q)$

Using Theorem 5.1 we can calculate the nimbers of the game
$BS_{2}(\mathcal{P}_{4}:p,q)$.

######  Theorem 6.1.

The nimber of the game $BS_{2}(\mathcal{P}_{4}:p,q)$ is $0$ for all $p,q\geq
3$.

###### Proof.

Observe that in the game tree of $BS_{2}(\mathcal{P}_{4}:p,q)$, the root has
exactly one child as the very first move is unique up to renaming of open
tips. Moreover, that child will have a child which can be expressed as a sum
of $CS_{4}(p,1,1,1)$ and $CS_{4}(1,1,q,1)$. As
$\eta[CS_{4}(t_{1},1,1,1)]\oplus\eta[CS_{4}(1,1,t_{3},1)]=0$ due to Theorem
5.1, the child of the root must have a non-zero nimber, and thus the root must
have its nimber equal to $0$. ∎

As a direct corollary, we can figure out which player has a winning strategy
in the game $BS_{2}(\mathcal{P}_{4}:p,q)$.

######  Corollary 6.2.

The second player has winning strategy in the game
$BS_{2}(\mathcal{P}_{4}:p,q)$ for all $p,q\geq 3$.

###### Proof.

As $\eta[BS_{2}(\mathcal{P}_{4}:p,q)]=0$ for all $p,q\geq 3$, the second
player must have a winning strategy. ∎

##  7 Conclusion

(1) In Section 1 we noticed that even though the game Brussels sprout is
defined on planar graphs, it can be played with the restriction of its
resultant graph belonging to any hereditary graph family. Naturally, such a
generalization of the game Sprout can also be considered. It is noteworthy,
that such generalizations of Sprout, especially, its play on different
surfaces, have been considered before [14]. It can be interesting to play both
the games for hereditary graph classes such as: graphs having bounded maximum
degree, graphs having bounded maximum average degree, planar graphs having
girth at least $g$ (for some $g\geq 4$) to name a few.

(2) In Corollary 2.4, we show that the winner of the game
$BS_{n}(\mathcal{O}_{k}:t_{1},t_{2},\cdots,t_{n})$ for $k\geq 1$, does not
change even if we vary $k$. A similar phenomenon has been noticed in the game
Sprout through a computer check [3]. To elaborate, a computer check reported
in [16] confirmed that the winner of the game Sprout (starting with $n$ dots)
does not change for small values of $n$. It is possible that Theorem 2.5
carries a theoretical insight of the underlying reasoning behind this
phenomenon.

(3) One of the major contributions of this article is to find out the nimber
of the game $CS_{4}(\mathcal{P}_{4}:p,1,q,1)$ for all values of $p,q\geq 0$
(see Section 5). We used the method of strong induction for the proof, and we
wonder if it is possible to attack Conjecture 1.1 using the same technique.
One of the major breakthroughs in applying this technique can come from
understanding how it may be possible to write a partially played Sprout game
as a sum of two other (similar) games.

(4) It may be interesting to explore a game where we start with some dots and
some spots having various numbers of open tips. The reason why this makes
sense and is relevant can be demonstrated via the following example.

$=$

Figure 4: A configuration of Sprout that can be replaced by a spot with three
open tips.

A partially played Sprout game may contain a connected component $C$ as
depicted in Fig. 4. In such a scenario, it is equivalent to considering the
game obtained by replacing $C$ with a spot having $3$ open tips.

(5) In this article we introduced the Circular sprout game and studied it for
the family of triangle-free planar graphs. The version we studied had only two
spots. Finding the nimber of this turned out to be a challenging problem.
Hence, finding the nimber of the Circular sprout games with multiple spots for
triangle-free planar graphs, and other hereditary families of graphs are
natural open problems.

(6) Last but not the least, is it possible to consider a circular version of
the game Sprout? That may actually help us to understand the nature of certain
subgames of Sprout.

Acknowledgements: We thank Prof. Gary MacGillivray for his valuable
suggestions. This work is partially supported by the following
projects:“MA/IFCAM/18/39”, “SRG/ 2020/001575”, “MTR/2021/000858”, “NBHM/RP-8
(2020)/Fresh”, and “ASEAN 1000 PhD Fellowship”.

## References

  * [1] M. Albert, R. Nowakowski, and D. Wolfe.  Lessons in play: an introduction to combinatorial game theory.  AK Peters/CRC Press, 2019.
  * [2] H. D. Allen.  Winning ways for your mathematical plays, vol. 2, (book).  Mathematics teacher, 97(1):78, 2004.
  * [3] D. Applegate, G. Jacobson, and D. Sleator.  Computer analysis of sprouts.  I Personal Magic, page 199.
  * [4] E. R. Berlekamp, J. H. Conway, and R. K. Guy.  Winning Ways for Your Mathematical Plays, Volume 3, volume 3.  CRC Press, 2018.
  * [5] A. Bezdek, H. Gilroy, O. Henderschedt, and A. Lakhani.  On Conway’s Brussels Sprouts.  Studia Scientiarum Mathematicarum Hungarica, 60(1):76–90, 2023\.
  * [6] C. Browne.  Algorithms for interactive sprouts.  Theoretical Computer Science, 644:29–42, 2016.
  * [7] G. Cairns and K. Chartarrayawadee.  Brussels sprouts and cloves.  Mathematics Magazine, 80(1):46–58, 2007.
  * [8] T. Čížek and M. Balko.  Implementation of sprouts: a graph drawing game.  In International Symposium on Graph Drawing and Network Visualization, pages 391–405. Springer, 2021.
  * [9] M. Copper.  Graph theory and the game of sprouts.  The American mathematical monthly, 100(5):478–482, 1993.
  * [10] R. Focardi and F. L. Luccio.  A modular approach to sprouts.  Discrete applied mathematics, 144(3):303–319, 2004.
  * [11] M. Gardner.  Mathematical games.  Scientific American, 216(6):124, 1967.
  * [12] C. Ji and J. Propp.  Brussels sprouts, noncrossing trees, and parking functions.  arXiv preprint arXiv:1805.03608, 2018.
  * [13] T. Lam.  Connected sprouts.  The American mathematical monthly, 104(2):116–119, 1997.
  * [14] J. Lemoine and S. Viennot.  Sprouts game on compact surfaces.  arXiv preprint arXiv:0812.0081, 2008.
  * [15] J. Lemoine and S. Viennot.  Computer analysis of sprouts with nimbers.  arXiv preprint arXiv:1008.2320, 2010.
  * [16] J. Lemoine and S. Viennot.  Nimbers are inevitable.  Theoretical Computer Science, 462:70–79, 2012.
  * [17] A. N. Siegel.  Combinatorial game theory, volume 146.  American Mathematical Soc., 2013.
  * [18] D. B. West.  Introduction to graph theory, volume 2.  Prentice hall Upper Saddle River, 2001.
  * [19] N. Williams.  Planted brussels sprouts (after ji-propp).  J. Integer Seq., 21(8):18–8, 2018.