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.

OldTrout, Going Postal

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 :

OldTrout, Going Postal

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\).

OldTrout, Going Postal

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\).

OldTrout, Going Postal

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