Game on empty graph

Question

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.

Answer 1

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.