11
$\begingroup$

Given positive integers $n$ and $d\leqslant n-1$. Two players build a graph, starting with $n$ vertices and no edges. On each turn, a player joins two yet not joined vertices by an edge. It is forbidden to get a vertex of degree greater than $d$. The player who has no legal move loses. Who wins?

If I am not mistaken or missing other source, this was proposed for $d=2$ and $n=2001$ by Dmitry Maximov to the math circle high school students. It appeared to be harder than expected, but I hope that I may prove that, for $d=2$, for $n=4m+1$ vertices the second player wins and for $n=4m+2$ vertices the first player wins.

Improve this question
$\endgroup$
4
  • $\begingroup$ Initially it looks like there is basically no obstruction at all to making a move, so you would just work out floor(nd/2) and see if it's even or odd. But the problem is that if right at the end you have most vertices of degree d and then the rest form a complete graph on d vertices, those vertices have degree d-1 and you can't join any two of them because they're already joined. So maybe the player with the parity advantage just has to make sure the graph is connected (which doesn't sound hard, at least if d is large enough) and then they should be OK? Or is it harder than this? $\endgroup$
    – Kevin Buzzard
    Commented Jan 26, 2017 at 8:48
  • $\begingroup$ Say, for $d=2$ the final configuration is several cycles or several cycles plus edge or several cycles plus vertex. The parity is not fixed. $\endgroup$
    – Fedor Petrov
    Commented Jan 26, 2017 at 8:58
  • $\begingroup$ Aah yes I see -- $d=2$ is rather small somehow; the player who wins the parity game has no chance of making the graph connected. Maybe for $d=2$ you have to do some work (which perhaps you already did) and for bigger $d$ the game gets easier? The parity guy just has to make sure that they keep connecting the components together before the other guy makes a subgraph where every vertex has degree $d$. Is $d=2$ the hardest case then? What is your actual question? To analyse the game completely for $d=2$? Do you want to play? :-) $\endgroup$
    – Kevin Buzzard
    Commented Jan 26, 2017 at 9:55
  • $\begingroup$ Even if the final graph is connected, it does not determine the parity of the number of edges. $\endgroup$
    – Fedor Petrov
    Commented Jan 26, 2017 at 11:28

1 Answer 1

Reset to default
2
$\begingroup$

When $d=2$, for the purposes of determining the legal moves we only care about whether each component is an isolated vertex, a single edge, or a path of length at least two. This structure is simple enough that we can solve the game efficiently by dynamic programming.

Here's an example in Haskell.

{-- 
 (vertices, edges, paths)

 We only guard explicitly against there being no path components, 
 as moves involving edge and vertex components use up those components,
 leading to illegal game states that will be detected in the next
 round.
--}

win' (0,0,0) = False   -- nothing at all
win' (1,0,0) = False   -- isolated vertex
win' (0,1,0) = False   -- single edge
win' (v,e,0) = not $ all win [(v-2,e+1,0),    -- join two vertices
                              (v-1,e-1,1),    -- extend edge by a vertex
                              (v,e-2,1)]      -- join two edges
win' (v,e,p) = not $ all win [(v,e,p-1),      -- close a cycle or join two paths
                              (v-1,e,p),      -- extend path by a vertex
                              (v,e-1,p),      -- extend path by an edge
                              (v-2,e+1,p),    -- join two vertices
                              (v-1,e-1,p+1),  -- extend edge by a vertex
                              (v,e-2,p+1)]    -- join two edges

cache = [ [ [win' (v,e,p) | p <- [0..] ] | e <- [0..] ] | v <- [0..] ]

win (v,e,p) | v < 0 || e < 0 || p < 0 = True -- opponent made an illegal move
win (v,e,p) = cache !! v !! e !! p

If we believe that there are no lingering bugs, the game appears to be decided by parity for $n$ sufficiently large (but not the parity that you would expect from the final state being a union of cycles).

*Main> [win (n,0,0) | n <- [1..100]]
[False,True,True,False,False,True,True,True,False,True,
 False,True,False,True,False,True,False,True,False,True,
 False,True,False,True,False,True,False,True,False,True,
 False,True,False,True,False,True,False,True,False,True,
 False,True,False,True,False,True,False,True,False,True,
 False,True,False,True,False,True,False,True,False,True,
 False,True,False,True,False,True,False,True,False,True,
 False,True,False,True,False,True,False,True,False,True,
 False,True,False,True,False,True,False,True,False,True,
 False,True,False,True,False,True,False,True,False,True]

This presumably leads to a formal proof by induction.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, it leads, the following argument is suggested by Alexander Kuznetsov: if for some $x$ the second wins for ($x$ points plus long path) and ($x+2$ points plus long path), he also wins for ($x+4$ points plus long path), starting from $x=6$ we get that the second wins for even (but at least 6) number of points plus the long path, it immediately yields that the second wins for odd (but at least 9) number of points, and the first wins for the even number of points (but at least 6). $\endgroup$
    – Fedor Petrov
    Commented Jan 26, 2017 at 12:20

You must log in to answer this question.

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