Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
The game starts with a graph with $n$ vertices and no edges. The players alternately add edges until the graph contains a hamilton-circle. The player who made the last move loses.
Who has a winning strategy in this game depending on the number of vertices ? For $n = 3$, the game is boring because player $2$ always wins, no matter how the play is. For $n=4$, player $2$ has a winning strategy.
Computation over all labeled graphs shows that for $n = 5$ and $n = 6$ the first player has a winning strategy, for $n = 7$ and $n = 8$ hasn't. My actual conjecture is the following: first player has a winnning strategy if and only if $n = 4k + 1$ or $n = 4k + 2$. The reason for my conjecture is that complete graph on $n - 1$ vertices has even number of edges in these cases. Also I have checked supposition that avoiding dummy moves (i. e., moves that end game instantly and undesirably) is good enough strategy, but no, it isn't even for $n = 5$.
