Edit: I made a mistake with some of the language here. A comment from a true graph theorist:

“Hamiltonian” usually means there’s a hamilton/hamiltonian cycle. Graphs with a hamilton path are “traceable”. Hamiltonian implies traceable, but not conversely.

Thus, I have edited below accordingly.

——————————-

There was a nice video up on Numberphile about a problem which could easily be explained to a school student, and yet we don’t yet know the answer to it. See the videos here:

and

The game is the following: Given a sequence of consecutive integers, draw a graph where the nodes are the integers and there is an edge between each integer if their sum is a square number.

If we take the numbers from 1 to 12, then the following would be the associated graph (note that there are three disconnected pieces of it).

Note that this is a disconnected, undirected graph. Looking at some of the edges. 12 is joined to 4 because 12+4=16 which is a square number. 4 is joined to 5 because 4+5 is a square numbers, etc.

This graph is disconnected, but if we go up to 14, we can create a graph which is connected:

(note that the self-c0nnected vertices are not important in any of this) The next question is, is there a Hamiltonian path in this graph? That is, is there a path that we can take, walking along the edges, which goes through each node once. The answer here is no, because, starting at 9, once we get to 3, we can either take the upper fork, or the lower fork, and we can’t turn back. Is there a graph where we can get a Hamiltonian path? The answer is yes, and the first one is at 15: The red line here is a Hamiltonian path.

You can continue on to see if 16 also gives such a Hamiltonian path, and indeed it does, as does 17, but 18 does not.

Is that it? Well, it turns out that you can continue going and you will find that the next number for which you can form the Hamiltonian path is 23, then 24 you can’t, then 25 you can and in fact it seems that as you add more and more numbers, you always can.

The fundamental question is: Is there a Traceable graph (see the edit at the beginning) for all numbers above 25? However, this has only been tested up to around 300 (according to the video) (Finding Hamiltonian paths is an NP complete problem). I wanted to see if we could do better than that, so I wrote a piece of Mathematica code to see what we could do. First, I will show the code, then we’ll talk through it:

OK, what do we have here? Well, let’s start in the middle and work out. The one input into the module is a variable upto which is simply the last integer in the sequence that we want to test (ie. 18 in the last graph we showed above).

The first thing is to define a table of values of where m and n run from 1 to upto. In fact it’s not this value we want, but we want to know whether this value is an integer, ie. whether m+n is itself a square number. We do this using the command IntegerQ, which outputs True if it’s an integer, and false if it’s not.

We are interested in the positions in the table where True occurs – ie. there will be a True at position {2,7} in the table as which is an integer, and therefore this will give True. Thus:

Position[Table[IntegerQ[\sqrt{m+n}],{m,upto},{n,upto}],True]

Will give us the table of positions. However, this will give us some degeneracy, as {2,7} and {7,2} will both give true, but don’t give us any new information. So we take all of these pairs, and sort them. So Sort[{2,7}]={2,7} but Sort[{7,2}]={2,7}. Now we just have to take the Union and we are done. There are other ways of doing this (ie. defining a SameTest function within Union).

Great, now let’s take these pairs, which denote the edges we want in our graph, and create the connections. This is done by taking the set of pairs (call it pairs) and passing it into the Undirected Edge function (let’s write o-o, where in the above code it is with solid circles) :

#[[1]]o-o#[[2]]&/@pairs

We then form a graph with this set of undirected edges:

g1=Graph[#[[1]]o-o#[[2]]&/@pairs,VertexLabels->”Name”]

Where the VertexLabel option just means that the vertices (or nodes) are labeled with the number that they correspond to.

OK, how about the complicated task of calculating the hamiltonian path here? That seems like the tricky part. Well, mathematically it is tricky, but using Mathematica it is incredibly simple. We simply use the FindHamiltonianPath function:

h1=FindHamiltonianPath[g1]

which outputs a Hamiltonian Path if one exists, and the empty set if one doesn’t. We can then take this and overlay it on the original graph.

HighlightGraph[g1,PathGraph[h1]]

And we’re done. We can label it using Labeled[] with “path” if h1 is non-empty, and “no path” if it is, just to see it clearly.

OK, what can we do with this? Well, we can see if we can go any further than the video above to see whether we can find a higher number which doesn’t give a Traceable Graph. Let’s do this using a simple For loop. This is not perfect Mathematica coding, but for this process it’s not going to slow us down too much. In fact, to do this, we will alter the above Module so that the output is simply

If[h1 === {}, “no path”, “path”]

because we are not interested in the graph itself (which gets very messy very quickly), but just whether there is any Hamiltonian path.

define a set of results:

results={}

To keep track of things which can evaluate this dynamically:

Dynamic[results]

Now simply loop through all integers and append the newest result to results:

For[n = 1, n <= 400, n++,
 res1 = {n, creategraph[n] // Timing};
 res = Append[res, res1];
 ]

I have included a Timing function here because something rather strange seems to happen for some values. This is most likely because for some graphs, finding the path is relatively easy, but for some numbers, there are many dead ends. It would be interesting to know why this is. The timing to find the Hamiltonian path for each integer (in a log plot) is:

A simple question here is: Is the time that it takes to find a Hamiltonian path truly a function of the graph itself, or is it more closely related to the implementation in Mathematica of FindHamiltonianPath?

In addition, to find a Hamiltonian path for a sequence up to n, can we use the Hamiltonian path for the sequence up to n-1 as a starting point?

It seems that at n=229 things get much much slower, but then for larger numbers, we can solve them again. For instance, for n=555 it takes about 3 seconds to calculate a Hamiltonian path. The time taken seems to be roughly linear in n, other than the outliers which don’t seem to follow an obvious path.

Anyway, some fun ideas and some simple questions there. Let me know if you have any thoughts or questions about this.

—–

Addendum. Note that there is an obvious sufficient condition for a graph not to be Traceable, and that is for there to be more than 2 vertices which are only connected each to one other vertex. It is clear in going from n=14 to n=15 that we go from having three ‘loose ends’ to having two. It is however not a necessary condition. Can it be shown that for no n>18 are there graphs with more than two loose ends? It seems that this should be a very simple problem to show…