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**