# A Hamiltonian Path in the Natural Numbers

In graph theory, a graph is a mathematical structure.  It has vertices and edges and we are interested in pairwise relationships.

A Hamiltonian path is a walk that visits each vertex exactly once, as opposed to a Eulerian path which visits each edge exactly once – see the Seven Bridges of Koenigsberg.

Hamilton was interested in paths and cycles (end up where you started) on the Platonic solids.

The Hamiltonian cycle of the dodecahedron :

Do the natural numbers, $$\Bbb N$$, have a Hamiltonian path such that they can be arranged into an order whereby adjacent numbers add to a square number?

The smallest number for which this is possible is $$n = 15$$.

The vertices $$1$$ and $$3$$ both have three associated edges.

The vertices $$8$$ and $$9$$ both have only one associated edge.

We have fifteen vertices and fifteen edges and we only need fourteen edges.

We can begin our Hamiltonian path at $$8$$ or $$9$$ and in both cases miss the edge between $$1$$ and $$3$$.

Hence, the natural numbers $$1, …, 15$$ can be ordered either :

$$8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9$$

or :

$$9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8$$

Note that the number of permutations of fifteen things is :

$$1,307,674,368,000$$

We can add $$16$$ to $$9$$ and $$17$$ to $$8$$ and have Hamiltonian paths for $$n = 16$$ and $$n = 17$$, however, it breaks down for $$n = 18$$ – there is no path.

There are no paths for $$n = 19, 20, 21, or \, 22$$ but we have a path for $$n = 23$$.

Note that $$18$$ has only one edge and start from there.

The path is :

$$18, 7, 9, 16, 20, 5, 11, 14, 2, 23, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22$$

Then $$n = 24$$ has no path.

The numbers $$n = 25$$ through to $$n = 299$$ have all been tested and all have paths.

Number theory meets graph theory.

© OldTrout $$2018$$

Audio file