Which graphs are winnable in Snake?

Let's consider the game of Snake; except instead of playing it on a grid, we're going to play it on an arbitrary finite [simple] graph. We assume the snake starts at length 1 -- the game begins by the "computer" (who acts adversarially) picking a starting spot for the snake and a starting spot for the fruit. When the snake consumes the fruit (and thereby grows by 1), the computer picks a new spot for the fruit, which cannot be somewhere currently covered by the snake. We'll say the player wins if the snake covers the whole graph. If the game goes on infinitely, I guess that's a draw, but we'll give it to the computer.

So the general question then is, for which graphs can the player always win? (Hence why I said draws go to the computer.) Now this question is not necessarily that concrete; there might not be any nice characterization. I have bunch of notes about necessary conditions and sufficient conditions for this, but I'm not going to list them all here.

(Here are some obvious ones -- if a spanning subgraph of a graph is winnable, then so is the whole thing; any cycle is winnable, so so is any graph with a Hamilton cycle; in order to be winnable, a graph must have a Hamilton path. But like I said, I'm not going to put all my notes here.)

So -- you'll notice I didn't give a totally formal specification of the rules above, and there's a reason for that. When you formalize the rules, you realize there's the question: Should a snake of length 2 be allowed to turn around? As in, move its head to the current location of the tail. If you write the rules in the obvious manner, this is entirely legal, but it seems kind of unintuitive. So we can have two variants of the game: The weak game, where this is allowed; and the strong game, where it is not. (Note that you could consider graphs with multiple edges, and say that then in the strong game you're allowed to turn around if there's a double edge; but I'm restricting to simple graphs for reasons you'll see shortly.)

There is at least one graph that is weakly winnable but not strongly winnable, namely, a path of length 3. So, question number one: Are there any other such graphs? I suspect the answer is no but have been unable to prove it. Hence the restriction to simple graphs -- if I'm right, then unless the "underlying simple graph" is P₃, adding multiple edges simply won't affect anything. (And it's easy to see how it affects P₃.)

But let's put that aside and return to the question of which graphs are winnable more generally. Here are some examples of winnable graphs:

• For n≥3, the cycle C_n.
• For n≥3, two copies of K_n joined at a vertex.
• For 1≤i≤j≤k, define Θ_i,j,k to be the graph consisting of two vertices and three paths between them, with i, j, and k vertices in the interior of the three paths (respectively). Then Θ_1,1,k is winnable.
• (Thanks to Justin Kopinsky for finding these!) For m≥2 and k≥1, take Θ_m,m,k, except that instead of using paths of length m, we use cliques of size m; moreover, each vertex in each clique is connected to both of the "hinge" vertices. Note that when m=1, this is just Θ_1,1,k from above, but I've listed this separately because I think it's easier to understand this way. Let's call this new graph Ψ_m,k.

Now above I've talked about winnable graphs, but I've found an alternative formulation helpful. If a graph has a spanning subgraph which is winnable, then the graph is winnable. Hence, rather than focusing on all winnable graphs, let's focus just on minimal winnables -- ones where deleting any edge renders the graph unwinnable. (Note: For the rest of this, I'm going to assume the strong game unless I say otherwise.) Characterizing these would characterize all winnable graphs, as a graph is winnable iff it contains some minimal winnable.

So far I've only managed to find a few types of minimal winnable graphs! And, more generally, every winnable graph I know of contains one of these as a spanning subgraph. There are of course the trivial ones -- the zero-vertex graph, the one-vertex graph, the path P₂. But the interesting ones are the following:

1. For n≥3, the cycle C_n. (In the weak game, we should restrict to n≥4, as there C₃ is not minimal.)
2. For n≥3, two copies of K_n joined at a vertex. (In the weak game, we should instead say n≥2, as n=2 yields the path P₃.)
3. The graphs Ψ_1,k=Θ_1,1,k.
4. The graphs Θ_2,2,k for k∈{1,2}, and, for k≥3, the graphs Ψ_2,k.
5. For m≥4, let's take Ψ_m,k and modify it as follows. For each vertex in one of the two cliques, connect it to only one of the two "hinge" vertices instead of both of them. As long as k≤m, any choice of how to do this should work, so long as each hinge vertex is in fact adjacent to each clique; if k>m, we require that each hinge vertex is adjacent to each clique via at least two edges.
6. For m=3, k≤3, we'll do the same thing as in the previous case; but if k>3, in each triangle, among the three vertices, one will connect to one hinge vertex, one to the other hinge vertex, and one to both.

(Note: Those last few I haven't quite fully checked, but I think they're right?)

So, question number two: Could this possibly be all of them? It seems unlikely, but it might just be possible. I have in fact verified that these are all of them up to 7 vertices, so any counterexample will have to be at least 8 vertices, unless I've messed up.

Note that an earlier version of this page only included families (1)-(3) above; so the original "are these all?" question has now been answered with a "no". Still, we can once again ask "are these all" about the new list!

I'd also like to ask, question number three: If one subdivides an unwinnable graph, is the result necessarily also unwinnable? I used to think I had a counterexample to this, but it turned out to be wrong! If these really are all the minimal winnables, then the answer to this question is positive, but I think it's also of independent interest!

Finally, we can ask about a variant of the game on an infinite graph. Here we can define "winning" as the snake increasing in length without bound. I mostly think this variant is less interesting, but I would like to ask question number four: Is there an infinite unwinnable graph without any cut-vertices? I'm guessing there probably is, but so far I haven't managed to find one!

Corrections:

An earlier version of this page erroneously claimed that I had checked all graphs of up to 8 vertices, but it turns out the method I used is only valid up to 7 vertices.

An earlier version of this page erroneously claimed that Θ_2,2,k is winnable for k≥3; this was part of more generally giving an incorrect minimization of Kopinsky's family (I said that the one-connection procedure sufficed for all m,k≥1, rather than it requiring k≤m.) It also used this to claim a counterexample to question number three, but this counterexample wasn't valid. Thanks to Rakesh Rivera, Enze Chen, Nathan Negera, and Janice Yuan for finding this error.

(back to main page)