13
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nice answer! (+1) $\endgroup$ – Peter Feb 1 '17 at 10:17
  • 1
    $\begingroup$ The next subresult for $n = 9$ is that the first player has a winning strategy and it confirms conjecture. $\endgroup$ – Smylic Feb 1 '17 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.