Game on empty graph 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.
 A: I will get you started with some observations.
First, every intermediate position is summarized by two parameters:

*

*$n_1, \dots, n_k$ with $n_1 + n_2 + \dots + n_k=n$: the number of vertices in each component.

*$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:

*

*$k_{\text{even}}$: the number of even components.

*$k_{\text{odd}}$: the number of odd components.

*$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.
