14
$\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$
0

1 Answer 1

6
$\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$
2
  • $\begingroup$ Nice answer! (+1) $\endgroup$
    – Peter
    Commented Feb 1, 2017 at 10:17
  • 2
    $\begingroup$ The next subresult for $n = 9$ is that the first player has a winning strategy and it confirms conjecture. $\endgroup$
    – Smylic
    Commented Feb 1, 2017 at 16:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .