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. I do, however, have two specific questions about this that I'd like to ask.

(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_{3}, adding multiple edges simply won't
affect anything. (And it's easy to see how it affects P_{3}.)

Here's a second question. When I initially mentioned this problem to John
Wiltshire-Gordon, he suggested that whether a graph is winnable or not should
depend only on its topology. But this is not so; I have examples of (weakly or
strongly) winnable graphs that can be subdivided to be made non-winnable.
However, I have been unable to find an example of a (weakly or strongly)
non-winnable graph which can be subdivided to be made winnable. So, **question
number two**: If a graph is non-winnable (weakly or strongly), is the same
true of any subdivision of it? For this question I don't really have a good
idea what the answer should be. My guess would be yes, but I wouldn't be all
that surprised if someone found a counterexample.

By the way, someone -- I forget who, unfortunately -- suggested that you could also play Snake on infinite graphs, with the win condition being that you grow arbitrarily large (now it's only a "draw" if the game goes on infinitely but your size stays bounded). But that seems like a pretty different problem, so I'm not going to consider that here.

UPDATE 1 July 2015:

Above I wrote that the question of which graphs are winnable might be too broad to answer. But actually it's possible -- I won't say likely, but possible -- that it might have a not-too-complicated answer.

Let's reformulate the question first. 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 this section, I'm
going to assume the strong game unless I say otherwise.) Characterizing these
would characterizing all winnable graphs, as a graph is winnable iff it contains
some minimal winnable.

Then 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_{2}. But the interesting ones
are the following:

- For n≥3, the cycle C
_{n}. (In the weak game, we should restrict to n≥4, as there C_{3}is not minimal.) - 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}.) - 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}, Θ_{1,2,k}, and Θ_{2,2,k}are examples of minimal winnable graphs.

So, **question number three**: 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 8 vertices, so any counterexample will have to be at least 9
vertices, unless I've messed up.

Note that a positive answer to this question would also imply a positive answer to question two. It would also imply a positive answer to question one, but that's because this proposition essentially just includes that; it isn't a nontrivial implication. I should say, if this is true, I don't expect it to be at all easy to prove; it's not actually something I expect at all to solve...