On the game of bridges and islands.

We have seen (p. 35) that the game of bridges reduces to the description by one or more continuous lines, without repetition, of all figures formed from straight lines or curves, in the plane or in space. This study is summarized in the following two theorems:

Theorem I. – In any geometrical network formed of straight lines or curves, the number of odd points is always zero or an even number.

This theorem is completely proved in the paper by Euler {223} (p. 31); one can also give the proof the following form: Let us denote by A, B, C, D, …, the various stations of the network, the various branch points, the line-ends; let P and Q be two neighbouring stations, that is, such that it is possible to go from P to Q by one or more paths without encountering other stations of the network. If one of these paths PQ is removed, the number of paths which end in P, and likewise in Q, decreases by one and changes parity. Consequently, if P and Q are odd points, they become even as a result of the removal; if P and Q are even, they become odd; finally if P and Q are of different parity, they remain of different parity. Thus number of odd points does not change parity as a result of this removal [11]. By removing one at a time all the paths that link two neighbouring stations, until there are none left, the number of odd points is nil; this number was therefore zero or an even number before the removal.
q. e. d.

Remark. – This theorem can be applied to geodetic surveys. In a chain of triangles, there is always an even number of vertices at which there meet an odd number of angles reduced to the horizon, whereas the number of vertices at which there meet an even number of triangles can be even or odd.

Theorem II. – Every geometric network containing 2n odd points can be described by a minimum of n unbroken lines without repetition. Every geometric network not containing odd points can be described by a single unbroken line without repetition.

We assume that the network is connected, i.e. that it is possible to pass from any point of the network to any other by a continuous route. Otherwise, in the case of several separate networks, it suffices to apply the preceding theorems to each of them. On that assumption, if we set out from an odd point A and move at random, but without passing twice over the same path, we shall sooner or later be brought to a halt; and noting that in the course of the journey we never change the parity of any station through which we pass, we conclude that the point where we halt is an odd point B. Removing the route AB, we thus obtain a figure that does not contain more than (2n − 2) odd points.

After n such journeys, there must remain a network all of whose stations are of even order.

Now, if we set out from any point M of the cut-down network, and move at random, we shall only be brought to a halt on arriving at the starting point M, after describing a closed curve. After describing a certain number of such loops, we shall have gone through the whole network. But, since the network is connected, these loops can be joined, {223} maybe one onto another, and then onto the n routes that were described to start with. Consequently, the network can be described by at most n unbroken lines.
q. e. d.

Remark. – A figure all of whose points are even can be considered, in several ways, as a single closed curve. This observation has a use in the theory of unicursal curves.



On the game of labyrinths.

The labyrinth problem is a particular case of the problem of bridges and islands; indeed, since one must traverse each path twice, it reduces to the problem of covering a network that contains only points of even order [12]. But, in this particular case, one can cover the network without knowing the plan of it, whereas this is no longer true in the general case.

The theory of trees is also reduces to Euler’s problem. Moreover it follows immediately from Theorem II of the preceding note that the number N, the basis of the tree, is equal to half of the number of odd points, i.e. the number l of free ends increased by the number of odd-order nodes. Let us denote by i the number of odd-order nodes, by j the number of even-order nodes; we have, referring back to the formulae on page 53,

N =  l + i    and    p = i + j.

By combining the various expressions for the number N, one can obtain several other formulae.

Remark. – In the first volume of the Théorie des Nombres [13], we have devoted a special chapter to the Geometry of position. This chapter contains many new developments of the game of bridges and islands and the game of labyrinths in the section entitled Les Réseaux.

One can find there other discussions on the use of arithmetic chess-boards, on polygons and polyhedra, on regions and on the theorems of Guthrie and Hamilton, Tait and G. Tarry.