A Special Complete Bipartite Graph

In December of 2024, I made a post titled Welcoming In 2025 in which I looked at some of the more interesting properties of the number 2025. Recently, in this YouTube video, I came across another interesting property of the number in connection to complete bipartite graphs and spanning trees.

The definition of a complete bipartite graph is a graph where all possible edges connect vertices in two disjoint sets, but no edge connects vertices in the same set. An example is \(K_{3,5} \) shown in Figure 1. The two disjoint sets have 3 and 5 vertices, hence the nomenclature.

A spanning tree is defined as a graph that connects all of a graph's vertices without creating any loops or cycles. It's a subgraph of the original graph, meaning it uses all of the vertices but only some of the edges.

An example of a spanning tree for \(K_{3,5}\) is shown in Figure 2 where the red edges represent the spanning tree.

There is a general formula for calculating the number of spanning trees for a \(K_{m.n} \) bipartite graph and it is:$$s(K_{3,5})=m^{n-1} n^{m-1}$$So in the case of \( K_{3,5} \) we have:$$s(K_{3,5})=3^4 5^2 = 2025$$Thus there are 2025 spanning trees for a complete \(K_{3,5}\) bipartite graph and thus we have another interesting property of this year's number.

The Reuleaux Triangle Revisited

In all my posts since the middle of 2015, I've only mentioned the Reuleaux (pronounciation) Triangle once and there's a good reason for this. Let's look at my original post from the 9th of November 2021 titled Reuleaux Triangle. I wrote (text in blue):

Today, having turned 26518 days old, I found an interesting property of this number that qualifies it for membership in OEIS A340644:

A340644

The number of vertices on a Reuleaux triangle formed by the straight line segments mutually connecting all vertices and all points that divide the sides into n equal parts.

 The initial members of the sequence are:

3, 19, 120, 442, 1332, 2863, 5871, 10171, 17358, 26518, 40590, 57757, 81735, 110209, 148158, 192184, 248772, 313105, 393429, 483283, 593490, 715528, 861660, 1022281, 1211811, 1418515, 1659108, 1919842, 2220204, 2543527, 2912751, 3308305, 3755922, 4233730, 4770150, 5340529, 5977071 

26518 corresponds to the case where \(n\) = 10 and this number stands in splendid isolation from its neighbours: 17358 (\(n\) = 9) and 40590 (\(n \) = 11). The former occurred before I started monitoring my diurnal age and the second will occur long after I'm dead. In my post, I included the image shown in Figure 1.

Figure 1

The post I made back then is a good one, if I do say so myself, and delves into some interesting properties and applications of the Reuleaux triangle. The reason the triangle has popped up again has to do again with my diurnal age (27336) but this time it's regions rather than vertices that are involved. The number is a member of OEIS A340639:

A340639

The number of regions inside a Reuleaux triangle formed by the straight line segments mutually connecting all vertices and all points that divide the sides into n equal parts.

The initial members of the sequence are:

1, 24, 145, 516, 1432, 3084, 6106, 10638, 17764, 27336, 41233, 58902, 82675, 111864, 149497, 194430, 250534, 316020, 395728, 487122, 596434, 720162, 865321, 1027974, 1216291, 1425348, 1664539, 1928022, 2226658, 2553204, 2920378, 3319536, 3764848, 4246638, 4780489, 5355414, 5988973 

As with the number mentioned in the earlier post, 27336 corresponds to the case of \(n\) = 10 and once again its neighbours (17764 and 41233) are far removed. The OEIS comments provide a link to a very colourful image of the regions. See Figure 2.

Figure 2: source

However, the regions can be seen more clearly perhaps in the case of \(n\) = 2. See Figure 3.

Figure 3: source

So it may be some time before the Reuleaux triangle gets a mention again because the only integers associated with it seem to relate to vertices and regions arising from the division of its sides into \(n\) equal parts.

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

Reuleaux Triangle

Today, having turned 26518 days old, I found an interesting property of this number that qualifies it for membership in OEIS A340644:

A340644

The number of vertices on a Reuleaux triangle formed by the straight line segments mutually connecting all vertices and all points that divide the sides into \(n\) equal parts.

 The initial members of the sequence are:

3, 19, 120, 442, 1332, 2863, 5871, 10171, 17358, 26518, 40590, 57757, 81735, 110209, 148158, 192184, 248772, 313105, 393429, 483283, 593490, 715528, 861660, 1022281, 1211811, 1418515, 1659108, 1919842, 2220204, 2543527, 2912751, 3308305, 3755922, 4233730, 4770150, 5340529, 5977071

26518 corresponds to the case where \(n=10\) and Figure 1 illustrates the situation:

Figure 1: source

The vertices referred to are best illustrated in the simplest non-trivial case of \(n=2\) where 19 vertices can be counted. See Figure 2.

Figure 2: source

The Reuleaux triangle has some very interesting properties but first a definition from Wikipedia:

A Reuleaux triangle is a curved triangle with constant width, the simplest and best known curve of constant width other than the circle. It is formed from the intersection of three circular disks, each having its centre on the boundary of the other two. Constant width means that the separation of every two parallel supporting lines is the same, independent of their orientation. Because all its diameters are the same, the Reuleaux triangle is one answer to the question "Other than a circle, what shape can a manhole cover be made so that it cannot fall down through the hole?"

Figures 3 and 4 illustrate what is mentioned in the definition:

Figure 3: Wikipedia

Figure 4: Wikipedia

The Reuleaux triangle has the smallest possible area of any curve of given constant width. This area is:$$ \frac{1}{2}(\pi - \sqrt{3}) \, s^2 \approx 0.77477 \, s^2 \text{ where } s \text{ is the constant width}$$At the other extreme, the curve of constant width that has the maximum possible area is a circular disk, which has area given by:$$ \frac{\pi \, s^2}{4} \approx 0.78540 \, s^2$$Wikipedia goes on to say that:

Any curve of constant width can form a rotor within a square, a shape that can perform a complete rotation while staying within the square and at all times touching all four sides of the square. However, the Reuleaux triangle is the rotor with the minimum possible area. As it rotates, its axis does not stay fixed at a single point, but instead follows a curve formed by the pieces of four ellipses. Because of its 120° angles, the rotating Reuleaux triangle cannot reach some points near the sharper angles at the square's vertices, but rather covers a shape with slightly rounded corners, also formed by elliptical arcs. Figure 5 illustrates this.

Figure 5

Interestingly, we also learn from the same source that:

Many guitar picks employ the Reuleaux triangle, as its shape combines a sharp point to provide strong articulation, with a wide tip to produce a warm timbre. Because all three points of the shape are usable, it is easier to orient and wears less quickly compared to a pick with a single tip.

Figure 6: source

To quote from the site:

APC™ Trident Pick

$35.00

The APC™ Trident is our take on an historic shape used by acoustic guitar players, electric players as well as mandolin players. This shape also has an interesting property, it is a curve with a consistent width also known as a Reuleaux triangle. The world’s first guitar pick that is true Reuleaux triangle. It can roll smoothly.

Another application of the shape, to quote again from Wikipedia, is:

The Reuleaux triangle has been used as the shape for the cross section of a fire hydrant valve nut. The constant width of this shape makes it difficult to open the fire hydrant using standard parallel-jawed wrenches; instead, a wrench with a special shape is needed. This property allows the fire hydrants to be opened by firefighters (who have the special wrench) but not by other people trying to use the hydrant as a source of water for other activities. Figure 7 illustrates this.

Figure 7

Clifford Pickover in his famous "The Math Book" has a section on the Reuleaux Triangle in which he writes:

Reuleaux Triangle 

Franz ReuIeaux (1829-1905)

The Reuleaux triangle (RT) is one example of a wide class of geometrical discoveries like the Mobius Strip that did not find many practical applications until relatively late in humankind's intellectual development. Not until around 1875, when the distinguished German mechanical engineer Franz Reuleaux discussed the famous curvy triangle, did the RT begin to find numerous uses. Although Reuleaux wasn't the first to draw and consider the shape formed from the intersection of three circles at the comers of an equilateral triangle, he was the first to demonstrate its constant-width properties and the first to use the triangle in numerous real-world mechanisms. The construction of the triangle is so simple that modem researchers have wondered why no one before Reuleaux had exploited its use. The shape is a close relative of a circle because of its constant width, meaning that the distance between two opposite points is always the same.

Various technology patents have focused on drill bits that cut square holes using the RT. At first, the notion of a drill that creates nearly square holes defies common sense. How can a revolving drill bit cut anything but a circular hole? But such drill bits exist For example, the illustration shown here is from the 1978 patent U.S. 4,074,778 for a "Square Hole Drill" and is based on the RT. The RT also appears in patents for other drill bits as well as for novel bottles, rollers, beverage cans, candles, rotatable shelves, gearboxes, rotary engines, and cabinets.

Many mathematicians have studied the Reuleaux triangle, so we know a lot about its properties. For example, its area is \( A = \frac{1}{2}(\pi - \sqrt{3}) \, r^2 \) and the area drilled by a RT drill bit covers 0.9877003907... of the area of an actual square. The small difference occurs because the Reuleaux drill bit produces a square with very slightly rounded corners. Figure 8 illustrates the patent design.

Figure 8

The Reuleaux Triangle also appears is architecture, especially Church architecture where it represents the Trinity. Figure 9 depicts a Reuleaux triangle shaped window of Sint-Salvatorskathedraal, Bruges.

Figure 9: source

Figure 10 shows the Trefoil knot, associated with the Borromean Rings. The Reuleaux Triangle is in the centre together with the three overlapping each being a vesica pisces.

Figure 10

This is just a small sampling of the properties and applications relating to the Reuleaux Triangle and much more could be written but I'll have to stop somewhere.