Editing Sprouts (game) (section)

==Brussels Sprouts==
[[File:Brussel Sprouts Game.png|thumb|A 2-cross game of Brussels Sprouts always lasts exactly eight moves]]
A variant of the game, named '''Brussels Sprouts''' after [[Brussels sprout|the cruciferous vegetable]], starts with a number of crosses, i.e. spots with four free ends. Each move involves joining two free ends with a curve, again not crossing any existing line, and then putting a short stroke across the line to create two new free ends. This game is finite, and the total number of moves (and thus the game's winner) is predetermined by the initial number of crosses: the players cannot affect the result by their play. Thus, this variant may be termed, after Conway's categorisation of mathematics itself, a "one player game".

Each move removes two free ends and introduces two more. Nonetheless, the game is bound to end as some free ends become isolated. With ''n'' initial crosses, the number of moves will, remarkably, always be 5''n''&nbsp;−&nbsp;2. Consequently, a game starting with an [[parity (mathematics)|odd]] number of crosses will be a first player win, while a game starting with an [[parity (mathematics)|even]] number will be a second player win regardless of the moves.

To prove this, first, we argue the game must end. Then, we will calculate precisely how many moves it needs to end. The game outcome is then implied, as already described.

Treat each cross as a [[graph (discrete mathematics)|graph]] with 5 vertices and 4 edges. In the starting position with ''n'' crosses, we have a [[planar graph]] with ''v'' = 5''n'' vertices, ''e'' = 4''n'' edges, ''f'' = 1 face, and ''k'' = ''n'' [[component (graph theory)|connected components]]. The [[Euler characteristic#Planar graphs|Euler characteristic for connected planar graphs]] is 2. In a [[connectivity (graph theory)|disconnected]] planar graph, we get 

{{Equation|1=1+k = f-e+v}}

After ''m'' moves, we have:
* ''e'' = 4''n'' + 4''m'' since at each move, the player adds 4 edges.
* ''v'' = 5''n'' + 3''m'' since at each move, the player adds 3 vertices.

Then by the above, we have

* ''f'' − ''k'' = 1 + ''e'' − ''v'' = 1 − ''n'' + ''m''

Next, note that every time we add a cross, we are ensuring that each side of this cross ends up with a [[degree (graph theory)|degree]] 1 vertex. Thus, throughout the game, every face has at least one degree 1 vertex. Yet, the number of degree 1 vertices is invariant throughout the game, and remains at 4''n''. Hence, ''f'' is at most 4''n''. 

From this, we see ''m'' = ''f'' − ''k'' − 1 + ''n'' is at most {{nowrap|5''n'' − 2}} (since ''k'' is at least 1 and ''f'' is at most 4''n''). So the game must terminate, and it must terminate in at most {{nowrap|5''n'' − 2}} moves. Now, we argue it must terminate in exactly {{nowrap|5''n'' − 2}} moves.

In the final configuration, no face can have more than one degree 1 vertex, since otherwise, we could connect them with a cross and there would still be a legal move. Every face has at least one such vertex, so it must end with exactly one such vertex. So in the final configuration, ''f'' is exactly 4''n''.

Similarly, in the final configuration, the graph must be connected, since the outer face gets at least one degree 1 vertex per connected component, and cannot have more than one such vertex. So, in the final configuration, ''k'' is exactly 1.

Thus, to obtain the final configuration, we must have had ''m'' = ''f''−''k''−1+''n'' = 4''n''−1−1+''n'' = 5''n''−2.

A combination of standard Sprouts and Brussels Sprouts can also be played. The game starts with an arbitrary number (''n'') of dots or crosses. At each turn, the player chooses to add either a dot, or a cross, along the line they have just drawn. The duration of the game lays between (2''n'') and ({{nowrap|5''n'' − 2}}), depending on the number of dots or crosses having been added.

For ''n'' = 1, starting with a dot, the game will end after 2 moves. Starting with a cross, it will end after 2 moves if the first player adds a dot, after 3 moves if they add a cross: hence the first player has a winning strategy for both the normal and the misère version. For ''n'' > 1, the analysis is not completed.