A game: building a bounded degree graph 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. 
 A: 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.
