We wish to arrange the natural numbers such that adjacent pairs of numbers sum to a square number.

Why can we find a Hamiltonian path for some numbers and not others?

For a Hamiltonian path, given a number of vertices, \(n\), then we need a minimum of \(n\, – 1\) edges.

Each vertex may only be visited once and the maximum numbers of vertices with just one associated edge is two.

\(\begin{array}{ccccccc}

V & E & E-V &0 & 1 & 2 & 3 \\

\hline

1 & 0 & -1 & 1 \\

2 & 0 & -2 & 2\\

3 & 1 &-2 & 1 & 2\\

4 & 1 & -3 & 2 & 2\\

5 & 2 & -3 & 1 & 4\\

6 & 3 & -3 & 1 & 4 &1 1\\

7 & 4 & -3 & 0 & 6 & 1\\

8 & 5 & -3 & 0 & 6 &2\\

9 & 6 & -3 & 0 & 6 & 3\\

10 & 7 & -3 & 0 & 6 & 4\\

11 & 8 & -3 & 0 & 6 & 5\\

12 & 9 & -3 & 0 & 6 & 6\\

13 & 11 & -2 & 0 & 5 & 7 & 1\\

14 & 13 & -1 & 0 & 3 &10 &1\\

15 & 15 & 0 & 0 & 2 & 11 & 2

\end{array}\)

where V is the number of vertices, E is the number of edges and the columns \(0-3\) show the number of vertices with that many edges.

Essentially, in this range, there not enough edges which leaves too many vertices have just one associated edge.

Things begin to change at \(13\) when two edges are added \(3 + 13\) and \(12 + 13\). This increases the \(E-V\) count.

\(14\) has the required number of edges, however, it has three vertices with only one edge and, thus, cannot be a Hamiltonian path.

With \(15\), we have just two vertices with one edge and we also have enough edges. In fact, we must disregard the edge between \(1\) and \(3\) because they have three associated edges and we begin the Hamiltonian path at either \(8\) or \(9\).

© OldTrout \(2018\)