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.

# Game on empty graph

combinatorial-game-theorygraph theory

Skip to content
# Game on empty graph

###### Related Question

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.

## Best Answer

I will get you started with some observations.

First, every intermediate position is summarized by two parameters:

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

onlycorrect 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:

So we can get a much more concise summary of all the

relevantfeatures of a position: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:

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.