Problem 1687

Solution:

Answer: David has a winning strategy if and only if $n \equiv 2 (\bmod 4)$.

Call a move illegal if it would cause an odd cycle to be formed for the first time. First we show that if $n$ is odd, then any strategy where Jacob picks a legal move if one is available to him causes him to win. Assume for contradiction that Jacob at some point has no legal moves remaining. Since the graph representing the game state has no odd cycle, it must be bipartite. Let $a$ and $b$ be the sizes of the two sets in the bipartition of the graph. If there is some edge not already added between the two sets, adding this edge would be a legal move for Jacob. Therefore the graph must be a complete bipartite graph with all of its $ab$ edges present. However, since $a + b = n$ which is odd, one of $a$ or $b$ must be even and thus the graph contains an even number of edges. Moreover, since it is Jacob's turn, the graph must contain an odd number of edges, which is a contradiction. Therefore Jacob has a winning strategy for all odd $n$.

Now consider the case where $n$ is even. Call a graph good if the set of vertices of degree at least 1 are in a perfect matching (a set of non-adjacent edges that includes every vertex of the graph). The key observation is that either player has a strategy to preserve that the graph is good while increasing the number of vertices of degree at least 1. More precisely, if the graph was good at the end of a player's previous turn and there are fewer than $n$ vertices of degree at least 1, then at the end of his current turn he can always ensure that: (1) the graph is good and (2) there are at least two more vertices of degree 1 since the end of his previous turn. Let $A$ be the set of vertices of degree at least 1 at the end of the player's previous turn and $B$ be the set of remaining vertices where $|B| > 0$. Since the vertices of $A$ have a perfect matching, $|A|$ is even, and since $n$ is even, so is $|B|$. If the other player adds an edge between two vertices of $A$, add an edge between two vertices of $B$. If the other player adds an edge between two vertices of $B$, add an edge between one of those vertices and a vertex of $A$ (but on the first round, when $A$ is empty, respond by adding an edge between two other vertices of $B$). If the other player adds an edge between a vertex in $A$ and a vertex in $B$, then since $|B|$ is even, there must be another vertex of $B$. Connect these two vertices in $B$ with an edge. None of these moves can form a cycle and thus are legal. Furthermore, all of them achieve (1) and (2), proving the claim.

We now show that David has a winning strategy if $n \equiv 2 (\bmod 4)$. Since the graph begins empty and therefore good, David has a strategy of legal moves to ensure that the graph contains a perfect matching after no more than $n$ moves. After this, let David implement any strategy where he picks a legal move if one is available to him. Assume for contradiction that there is a turn where David has no legal moves. This graph must be a complete bipartite graph containing a perfect matching. If one of the sets in the bipartition has size greater than $n / 2$, it must contain two vertices matched in the perfect matching, which is impossible. Therefore there are $n / 2$ vertices in each part and $n^2 / 4$ edges have been added in total, which is an odd number. This contradicts the fact that it is David's turn, and proves the result for $n \equiv 2 (\bmod 4)$.

Finally, consider the case that $n \equiv 0 (\bmod 4)$. Note that after David's first turn, the graph contains a single edge and thus is good. This implies that Jacob can ensure the graph contains a perfect matching and win by the above parity argument.