Hamiltonian Paths Revisited

On the 6th February 2021, I posted about Hamiltonian Paths and Knight's Tours. That was over two years ago now but today I have the opportunity to revisit the topic of Hamiltonian paths because the number associated with my diurnal age, 26996, is a member of OEIS A003778:

A003778

Number of Hamiltonian paths in \(P_5 \times P_n \).

In the case of 26996, \(n=6\).  Figure 1 shows such a \(5 \times 6 \) grid.

Figure 1

A Hamiltonian path is one that passes through every vertex exactly once. One example of such a path is shown in Figure 2. Note that in this 2D grid connections between vertices or nodes are made up-down and left-right but not diagonally.

Figure 2

In the case of a \(5 \times 6\) grid, there are 26996 such paths that can be drawn. The number of paths increases rapidly as the number of points increases. Here are the initial values:

• \(5 \times 1 \rightarrow 1\)
• \(5 \times 2 \rightarrow 22\)
• \(5 \times 3 \rightarrow 132\)
• \(5 \times 4 \rightarrow 1006\)
• \(5 \times 5 \rightarrow  4324\)
• \(5 \times 6 \rightarrow 26996\)
• \(5 \times 7 \rightarrow  109722\)
• \(5 \times 8 \rightarrow 602804\)
• \(5 \times 9 \rightarrow 2434670\) 
• \(5 \times 10 \rightarrow 12287118\)

Here is a permalink to some Python code that will plot a Hamiltonian path through a grid of specified size. Figure 3 shows the output in the case of a \(5 \times 6\) grid:

[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 5), (1, 4), (1, 3), (1, 2), (1, 1), (1, 0), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (3, 5), (3, 4), (3, 3), (3, 2), (3, 1), (3, 0), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5)]

Figure 3

This YouTube video does a good job of explaining in simple terms the difference between a Hamiltonian path and an Euler path. For the latter, the path must traverse every edge exactly once whereas in the former it is every vertex that must be traversed.

There is a 36-term linear recurrence mentioned in the OEIS A003778 comments which is the closest thing to a formula that seems to be available for calculating the number of possible paths. Hamiltonian paths and cycles are intimately connected with the travelling salesman problem as this site explains:

Travelling Salesman Problem (TSP): 

Given a set of cities and the distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point. Note the difference between Hamiltonian Cycle and TSP. The Hamiltonian cycle problem is to find if there exists a tour that visits every city exactly once. Here we know that Hamiltonian Tour exists (because the graph is complete) and in fact, many such tours exist, the problem is to find a minimum weight Hamiltonian Cycle. 

Figure 4

For example, consider the graph shown in the Figure 4 on the right side. A TSP tour in the graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80. The problem is a famous NP-hard problem. There is no polynomial-time know solution for this problem. 

The site goes to provide programming solutions to this particular instance of the TSP but the Python3 solution doesn't work. However, the minimum cost Hamiltonian tour is  80 and 1-2-4-3-1 is one solution. This YouTube video offers a useful tutorial on how to draw graphs, such as the one shown in Figure 3, using SageMath.

I discovered an interesting site called Graph Online that allows you to create graphs and find Hamiltonian and Eulerian paths and cycles as well as Adjacency and Incidence Matrices. Figure 5 shows the Hamiltonian path that it came up with for the graph that I drew. No Hamiltonian cycle is possible.

Figure 5

Figure 6 shows a Eulerian path. No Eulerian cycle is possible. The site will display and analyse many other types of graphs. I've just focused on two here.

Figure 6