Translated from “Géométrie de situation: Nombre de manières distinctes de parcourir
en une seule course toutes les allées d’un labyrinthe rentrant, en ne passant qu’une
seule fois par chacune des allées”,
Compte rendu de l’Association française pour l’Avancement des Sciences,
15eme session (1886), pt. 2, 49–53 + Plates I & II.
In his paper on the Königsberg bridges, Euler stated that if a finite connected graph has an even number of edges at each vertex then it is possible to walk round the graph in such a way that every edge is traversed once and once only. In the paper below, Tarry shows how to calculate the number of ways in which this can be done.
As Euler showed, every such walk returns to its starting point. Tarry’s convention for counting the walks is that reversing the direction of a walk creates a different one, but changing the starting point does not.
{49}
By a re-entrant [rentrant] labyrinth I mean a labyrinth such that at every node of its path there are an even number of alleys.
The nodes at which there are more than two alleys will be called the junctions of the labyrinth.
I shall distinguish by the name loop [impasse] every alley whose endpoints are at the same junction.
{50}
If in a re-entrant labyrinth a loop is deleted, the number of different walks of the reduced labyrinth, multiplied by the number of its alleys ending at the junction on the deleted loop, is equal to the number of different walks of the original labyrinth. Note that any other loops attached to that junction should each be counted as two alleys.
Denote by N the number of different walks of the reduced labyrinth, and by 2n the number of its alleys ending at the junction on the deleted loop.
I say that the number of different walks of the original labyrinth is equal to N×2n [14].
Indeed, consider any one of the N different walks of the reduced labyrinth.
In this walk we shall pass n times through the junction where the loop was deleted, and on any one of those passages we can interrupt the walk on arriving at that junction, make a circuit of this loop, which can be done in two different directions, and, having returned to the junction, finish the walk that we began.
From this it follows that each of the N walks of the reduced labyrinth will provide 2n different walks of the original labyrinth.
The N walks of the reduced labyrinth will thus provide N×2n walks of the original labyrinth.
It is clear that these N×2n walks of the original labyrinth are all different, and that there are no other ways to traverse the original labyrinth in a single walk.
The theorem is therefore proved.
If at a junction there are 2(n+k) alleys, of which 2k belong to k loops, the number of different walks of the labyrinth in question is equal to the product of n(n+1)(n+2).....(n+k−1)2k by the number of different walks of the reduced labyrinth obtained by removing the k loops from the labyrinth in question.
Indeed, adding each of these k loops in turn to the reduced labyrinth amounts to multiplying the number of different walks by 2n, 2(n+1), 2(n+2),....2(n+k−1).
It will be seen that the loop theorem allows us to eliminate loops from the labyrinth in question and to reduce the calculation of the number of different walks to the case where the labyrinth no longer has any loops.
{51}
Given a re-entrant labyrinth without loops and comprising k junctions, if we denote by 2n the number of alleys ending at one of its junctions N, then the number of different walks of the labyrinth in question is equal to the sum of the number of different walks of 1×3×5×7..... (2n−1) re-entrant labyrinths comprising not more than (k−1) junctions.
These 1×3×5×7..... (2n−1) new labyrinths are obtained by grouping in pairs, in all possible ways, the 2n alleys ending at the junction N, and then replacing, in each of these groupings, every pair of alleys by a new alley joining the two junctions at the end of these alleys, or, in the special case where both alleys of the pair end at the same junction, by a loop passing through that junction.
Let us group the 2n alleys of the junction N into pairs of alleys, in all possible ways.
We thus obtain (2n−1)(2n−3).....5×3×1 different groupings.
With each of these groupings let us associate all walks of the labyrinth in question in which, at every passage through the junction N, the alley that leads into it and the alley that leads away from it belong to the same pair of that grouping.
It is easy to see that the required number of walks will be equal to the sum of the numbers of different walks corresponding to each grouping, in the way we have just indicated.
Granting that, let us consider the walks of one of these groupings, and let us examine the pairs of alleys that compose it.
In every one of these n pairs, the two alleys, considered as exits from the junction N, lead either to two different junctions A, B, or to the same junction C.
In the first case, we can obviously replace the two alleys NA and NB by a new alley AB, linking the junctions A and B, since that amounts to replacing the moves ANB or BNA by the equivalent moves AB or BA.
In the second case, it is equally clear that the two alleys linking the junctions N and C can be replaced by a loop passing through the junction C.
The theorem is therefore completely proved.
When we apply to new labyrinths the same method of eliminating loops and reducing the number of junctions, we shall {52} necessarily, by successive reductions, reach the point where we have only to consider labyrinths without loops and containing only two junctions, and the problem can then be solved.
Indeed, it can be shown very easily that the number of different walks of a labyrinth containing only two junctions joined by 2n alleys is equal to 2(2n−1)(2n−2)…4×3×2×1, if the direction of the walk is taken into account.
Remark. — A labyrinth that has only two odd vertices can also be traversed in its entirety by a single walk passing only once through each alley.
It is easy to see that the number of different walks of this labyrinth is the same as for the re-entrant labyrinth obtained by adding a new alley linking the two odd vertices.
See plates I and II for the application of the method to calculate the number of different walks of the re-entrant labyrinth whose alleys form the sides and diagonals of a heptagon.
The circles represent the junctions of the labyrinth.
The straight lines that link two circles represent the alleys of the labyrinth that link two junctions.
Loops, that is alleys whose ends are at the same junction, are shown as an equilateral triangle with a vertex on the circle corresponding to that juncion.
The identifying letter by each diagram is used in the calculation to represent the number of walks corresponding to that diagram, after removal of any triangles (loops) that it may have.
All diagrams that have the same form, after such reduction, are naturally denoted by the same letter.
The isolated number placed beside each diagram shows how many times the number of walks of the complete diagram must be counted.
Beside each diagram is placed the calculation of the number that must multiply the number of walks of the reduced diagram, in virtue of the loop theorem.
If the identifying letter of each diagram denotes the number of walks corresponding to the reduced diagram, we have the following table:
| X | = | 15H | T1 | = | 6D1 + 144D2 | |
| H | = | 8P1 + 4P2 + 8P3 + 4P4 | T2 | = | 2D1 + 16D2 | |
| T3 | = | 12D2 | ||||
| P1 | = | 6Q1 + 4Q2 + 16Q3 + 16Q4 | T4 | = | 2D2 + 4D3 | |
| P2 | = | 8Q1 + 16Q3 + 2Q5 + 16Q6 | T5 | = | D1 | |
| P3 | = | 2Q1 + Q2 | ||||
| P4 | = | 2Q1 + Q5 | D1 | = | 240 | |
| D2 | = | 12 | ||||
| Q1 | = | 6T1 + 24T2 + 48T3 | D3 | = | 2 | |
| Q2 | = | 8T1 + 24T2 + 64T4 | ||||
| Q3 | = | 2T1 + 4T2 | ||||
| Q4 | = | 2T2 + 4T3 | ||||
| Q5 | = | 48T2 + 24T5 | ||||
| Q6 | = | 2T2 + 2T5 |
{53} On carrying out the calculations shown in this table, we find that the required number of walks X is equal to 129,976,320 [15].
Important remark. – Two diagrams have the same number of walks if they can be made to correspond, junction for junction, in such a way that the number of alleys linking any two junctions in one of the diagrams is equal to the number of alleys linking the corresponding junctions in the other diagram.
The use of this theorem, which is almost intuitive, considerably reduces the labour by allowing us to give the same representation for diagrams that arise in different shapes.
Thus all hexagons can be represented by the same diagram H.