Sprouts (game) - Brussels Sprouts

A variant of the game, called Brussels Sprouts, 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.

So each move removes two free ends and introduces two more. Despite this, the game is finite, and indeed the total number of moves is predetermined by the initial number of crosses: the players cannot affect the result by their play. With n initial crosses, the number of moves will be 5n−2, so a game starting with an odd number of crosses will be a first player win, while a game starting with an even number will be a second player win regardless of the moves.

To prove this (assuming that the game ends), let m denote the number of moves and v,e,f denote the number of vertices, edges, and faces of the planar graph obtained at the end of the game, respectively. We have:

• e = 2m since at each move, the player adds 2 edges.
• v = n + m since at each move, the player adds one vertex (and the game starts with n vertices).
• f = 4n since there is exactly one free end in each face at the end of the game, (and the number of free ends does not change during the game).

The Euler characteristic for planar graphs is 2, so 2 = f-e+v = 4n-2m+n+m = 5n-m, hence m = 5n-2.