Path achievement games.
Ian M. Wanless · 2001
Starting with the empty graph on n vertices, two players alternately add edges until the graph contains a p-path. The last player to move wins. Assuming both players play optimally, the winner will depend only on p and n. We analyse the game for p::; 6 and arbitrary n, determining the winner and providing a winning strategy. The results illustrate how deceptive computing the results of small cases can be. The p-path achievement game is played by two players as follows. The game graph G starts off as K n (that is, n isolated points), for some n> p. The first player to move is designated Player A (or simply A), and the other player is known as Player B (or B). These two players take turns to add a single undistinguished