On the periodicity of graph games

Starting with the empty graph on p vertices, two players alternately add edges until the graph has some property P. The last player to move loses the P-avoidance game (there is also a P-achievement game, where the last player to move wins). If P is a property enjoyed by the complete graph on p vertices then one player must win after a finite number of moves. Assuming both players play optimally, the winner will depend only on p. All the games solved in the literature have followed a certain pattern. Namely, for sufficiently large p, the winner has been determined by the residue of p mod 4. We say such a game has a period of 4 (or in some cases a proper divisor of 4). In this paper we exhibit avoidance games with arbitrarily large period. We also prove that the equivalent games of 4-cycle achievement and 3-path avoidance have period 7.