# Game on empty graph

combinatorial-game-theorygraph theory

Given the empty graph with $$n$$ vertices. Alice and Bob alternately add one edge to that graph. The person who makes graph connected wins. Who has the winning strategy if Alice moves first.

I will get you started with some observations.

First, every intermediate position is summarized by two parameters:

1. $$n_1, \dots, n_k$$ with $$n_1 + n_2 + \dots + n_k=n$$: the number of vertices in each component.
2. $$a$$: the total number of edges absent from any component.

We don't care which component the absent edges are from: they just tell us how many moves can be made without combining two components.

Second, it's enough to only keep track of whether $$a$$ is even or odd. That's because, when $$a$$ is even, even if $$a>0$$, playing one of the absent edges is never the only correct move. If it were, your opponent would respond by playing another absent edge, and $$a$$ would return to being even and the position would otherwise stay the same. (Formally, we can prove "only the parity of $$a$$ matters" by induction on the number of edges not yet played.)

Finally, since we only care about the parity of $$a$$, we also mostly don't care about the sizes of the components. The only thing that matters about them is:

• If we connect two odd components, we get an even component, and the parity of $$a$$ does not change.
• If we connect two even components, we get an even component back (net loss of one even component), and the parity of $$a$$ changes.
• If we connect an even and odd component, we get an odd component back (net loss of one even component), and the parity of $$a$$ changes.

So we can get a much more concise summary of all the relevant features of a position:

1. $$k_{\text{even}}$$: the number of even components.
2. $$k_{\text{odd}}$$: the number of odd components.
3. $$a \bmod 2$$: the parity of the number of absent edges.

From here, we can continue with an N-position/P-position analysis. A position in the game is an N-position if it's a win for the Next player to move, and a P-position is a win for the Previous player. We can find these recursively, using the rule that:

• If there are only two components left ($$k_{\text{even}} + k_{\text{odd}} = 2$$), it's an N-position: the next player can join the two components and connect the graph.
• If all moves from the current position lead to N-positions, the current position is a P-position.
• If there is a move from the current position to any P-position, the current position is an N-position.

Use these rules to build a table of N-positions and P-positions; if you are lazy, use a computer. Find a pattern, and prove it by induction. The empty graph has $$(k_{\text{even}}=0, k_{\text{odd}} = n, a \bmod 2 = 0)$$, so once you know the values of $$n$$ for which this is an N-position, you know the values of $$n$$ for which Alice wins.