The Connect Game
Two friends are playing the following game:
They start with 10 nodes on a sheet of paper and, taking turns, connect any two of them which are not already connected with an edge. The first player to make the resulting graph connected loses.
Who will win the game?
Remark: A graph is “connected” if there is a path between any two of its nodes.
The first player has a winning strategy.
His strategy is with each turn to keep the graph connected, until a single connected component of 6 or 7 nodes is reached. Then, his goal is to make sure the graph ends up with either connected components of 8 and 2 nodes (8-2 split), or connected components of 6 and 4 nodes (6-4 split). In both cases, the two players will have to keep connecting nodes within these components, until one of them is forced to make the graph connected. Since the number of edges in the components is either C^8_2+C^2_2=29, or C^6_2+C^4_2=21, which are both odd numbers, Player 1 will be the winner.
Once a single connected component of 6 or 7 nodes is reached, there are multiple possibilities:
- The connected component has 7 nodes and Player 2 connects it to one of the three remaining nodes. Then, Player 1 should connect the remaining two nodes with each other and get an 8-2 split.
- The connected component has 7 nodes and Player 2 connects two of the three remaining nodes with each other. Then, Player 1 should connect the large connected component to the last remaining node and get an 8-2 split.
- The connected component has 7 nodes and Player 2 makes a connection within it. Then, Player 1 also must connect two nodes within the component. Since the number of edges in a complete graph with seven nodes is C^7_2=21, eventually Player 2 will be forced to make a move of type 1 or 2.
- The connected component has 6 nodes and Player 2 connects it to one of the four remaining nodes. Then, Player 1 should make a connection within the connected seven nodes and reduce the game to cases 1 to 3 above.
- The connected component has 6 nodes and Player 2 connects two of the four remaining nodes. Then, Player 1 should connect the two remaining nodes with each other. The game is reduced to a 6-2-2 split which eventually will turn into either an 8-2 split, or a 6-4 split. In both cases Player 1 will win, as explained above.
We do not know where this puzzle originated from. If you have any information, please let us know via email.