Brussels Sprouts and the Euler Characteristic

The Game

Brussels Sprouts is a two-player game about partitioning space. To begin a game of sprouts, draw a few seeds on a piece of paper. A seed is a point with any number of short edges coming out of it. Once you have drawn some seeds, the game begins. A move in sprouts consists of drawing a curve connecting two free line segments, then drawing a short line through the curve to create two new free line segments. Curves are not allowed to intersect each other, so as the game progresses more and more moves will become blocked. The last player to make a legal move is the winner.


A starting position in Brussels Sprouts	After one move	After two moves	A completed game of Brussels Sprouts

Strategy

How much strategy seems to be involved in a game of Brussels Sprouts?
If you start from a single seed (with any number of edges), how long will the game last?
What if there are two seeds to begin with? More than two?

Planar Graphs

When a game of Brussels Sprouts is completed, you are left with what mathematicians call a planar graph. This is a collection of points in the plane, connected by curves which do not cross each other. Planar graphs have many special properties: for example, take any finished game of Brussels Sprouts and four different colored pens. By being clever enough, you can always find a way to color each intersection with one of the four colors without ever giving two neighboring intersections the same color. Try it on your completed Brussels Sprouts games!

Planar graphs also always have a very particular relationship between the number of intersections, edges, and regions. Take any finished game of Brussels Sprouts. Add up the number of intersections, subtract the number of curves, and add the number of regions (don't forget to count the outside as a region!) and call the result E. E is called the Euler characteristic of the planar graph. Try computing E for many different finished games of Brussels Sprouts. What do you find each time?

Predicting Brussels Sprouts Games

By using the Euler characteristic, you can predict how long a game of Brussels Sprouts will last. If you know how long the game will last, you know who will win! Since the winner is the last person with a legal move, the first player wins every game with an odd number of moves, and the second player wins every game with an even number of moves.

How does the number of edges e in the finished Brussels Sprouts game relate to the number of moves?
Can you figure out how to predict the number of intersections i in a finished Brussels Sprouts game?
How many regions r are left at the end of the game?
Use the formula for Euler characteristic of a planar graph 2 = i - e + r to predict how long the game will last. Can you predict who will win the game by looking at the initial position?

Other Geometries

There is a bit more strategy involved when Brussels Sprouts is played on other surfaces, such as a donut or a Mobius strip. These spaces have a different Euler characteristic from the sphere, so the formula you found for the length of a game will need modification. Can you figure out how Brussels Sprouts works on

a Torus?
a Mobius strip?
a Klein bottle?
a Cylinder?
a Two-holed torus?
the Projective Plane?

If you ever woke up and discovered that you were living on one of these surfaces, could you figure out which one just through playing Brussels Sprouts?