### Another question about Snake

Jun. 30th, 2015 03:22 amThe broad question about Snake, which earlier I wrote might just be too broad to answer, was "Which graphs are winnable?" (Weakly or strongly.) But it is possible -- not likely, I don't think, but possible -- that this 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: 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:

1. For n≥3, the cycle C

_{n}. (In the weak game, we should restrict to n≥4, as there C

_{3}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}.)

3. For 1≤i≤j≤k, define G

_{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 G

_{1,1,k}, G

_{1,2,k}, and G

_{2,2,k}are examples of minimal winnable graphs.

So, the question: 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.

**EDIT 4 July 2015**: I may indeed have messed up about the 8-vertex case. I'm certain about the 7-vertex case, though. Will update if I fully solve the 8-vertex case. (9-vertex is out of reach, I think.)

Note that a positive answer to this question would also imply that subdivisions of unwinnable graphs are unwinnable, answering that question from the previous post. (It would also answer the question of whether weak and strong winnability coincide aside from P

_{3}, 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...

(I will update my website with all this later.)

(Also, "minimal winnable" is really fun to say. :) )

-Harry