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

Lines and Triangles

Consider the following problem as shown in Figure 1.

Figure 1

I just stumbled upon this problem, or rather a generalisation of this problem, and thought its solution was worthy of a mention. The solution was quite simple once I read it. Let's first review what the diagram shows. There are three parallel lines (labelled 1, 2 and 3) and another five non-parallel lines (labelled 4 to 8) that intersect with each other and also with the parallel lines. No three lines pass through a single point. How many triangles are formed?

Let's break the problem into two parts. Firstly let's deal with the five non-parallel lines. It takes three lines to make a triangle and so there are$$ \binom 5 3 = \binom 5 2 =\frac{5 \times 4}{2 \times 1}= 10 \text { possible combinations}$$So the five non-parallel lines form 10 triangles with each other. The three parallel lines can each be linked to a pair of non-parallel lines. This becomes:$$ \binom 5 2 \times 3 = 10 \times 3 = 30 \text{ possible combinations}$$So in total there are \(10 + 30 = 40\) triangles formed.

Generalising this, if there are \( n \) non-parallel lines and \(m\) parallel lines then:$$\text {The number of triangles formed is given by } \binom n 3 + \binom n 2 \times m$$Of course if none of the lines are parallel then \(m=0\) and the expression simplifies accordingly. It's interesting to count the number of points as well (shown in Figure 2):

Figure 2

The intersection of the lines produces 25 points, which I dutifully counted and labelled. If the points are taken in pairs, then each pair will generate a line with the result that there will be \( \binom {25} 2 = \frac {25 \times 24}{2 \times 1}=300\) lines which is clearly not the case because many of the lines are the same as others due to the large number of collinear points. 

However it can be noted that when two lines intersect, a point is created and so the following expression arises:$$ \binom 5 2 + 5 \times 3 = 10 + 15 =25 \text { which confirms my manual count}$$This can be generalised to:$$ \text {The number of points is given by }\binom n 2 + n \times m$$