PG26839.B00160
[PDF page 159] CHAPTER VI. UNICURSAL PROBLEMS. I proposeto consider in this chapter some problems which arise out of the theory of unicursal curves. I shall commence withEuler’s Problem and Theorems, and shall apply the results briefly to the theo- ries ofMazes andGeometrical Trees. The reciprocal unicursal problems of theHamilton Gameand theKnight’s Path on a Chess-boardwill be discussed in the latter half of the chapter. Euler’s Problem. Euler’s problem has its origin in a memoir† presented by him in 1736 to the St Petersburg Academy, in which he solved a question then under discussion as to whether it was possible to take a walk in the town of Königsberg in such a way as to cross every bridge in it once and only once. The town is built near the mouth of the river Pregel, which there takes the form indicated on the following page and includes the island of Kneiphof. In 1759 there were (and according to Baedeker there are still) seven bridges in the positions shown in the diagram, and it is easily seen that with such an arrangement the problem is insoluble. Euler however did not confine himself to the case of Königsberg, but discussed the general problem of any number of islands connected in any way by bridges. It is evident that the question will not be affected if † Solutio problematis ad Geometriam situs pertinentis, Commentarii Academiae Scientiarum Petropolitanaefor 1736, St Petersburg, 1741, vol.viii, pp. 128–140. This has been translated into French by M. Ch. Henry; see Lucas, vol.i, part 2, pp. 21–33. 143

PG26839.B00161
[PDF page 160] 144 UNICURSAL PROBLEMS. [CH. VI we suppose the islands to diminish to points and the bridges to lengthen out. In this way we ultimately obtain a geometrical figure or network. In the Königsberg problem this figure is of the shape indicated below, the areas being represented by the pointsA, B, C, D, and the bridges being represented by the linesl, m, n, p, q, r, s. A B C D s r l qp mn Euler’s problem consists therefore in finding whether a given ge- ometrical figure can be described by a point moving so as to traverse every line in it once and only once. A more general question is to deter- mine how many strokes are necessary to describe such a figure so that no line is traversed twice: this is covered by the rules hereafter given. The figure may be either in three or in two dimensions, and it may be represented by lines, straight, curved, or tortuous, joining a number of given points, or a model may be constructed by taking a number of rods or pieces of string furnished at each end with a hook so as to allow of any number of them being connected together at one point. The theory of such figures is included as a particular case in the

PG26839.B00162
[PDF page 161] CH. VI] EULER’S PROBLEM. 145 propositions proved by Listing in hisTopologie*. I shall, however, adopt here the methods of Euler, and I shall begin by giving some definitions, as it will enable me to put the argument in a more concise form. A node (or isle) is a point to or from which lines are drawn. A branch (or bridge or path) is a line connecting two consecutive nodes. An end (or hook) is the point at each termination of a branch. The order of a node is the number of branches which meet at it. A node to which only one branch is drawn is afree node or a free end. A node at which an even number of branches meet is aneven node: evidently the presence of a node of the second order is immaterial. A node at which an odd number of branches meet is anodd node. A figure is closed if it has no free end: such a figure is often called a closed network. A route consists of a number of branches taken in consecutive order and so that no branch is traversed twice. A closed route terminates at the point from which it started. A figure is describedunicursally when the whole of it is traversed in one route. The following are Euler’s results. (i) In a closed network the num- ber of odd nodes is even. (ii) A figure which has no odd node can be described unicursally, in a re-entrant route, by a moving point which starts from any point on it. (iii) A figure which has two and only two odd notes can be described unicursally by a moving point which starts from one of the odd nodes and finishes at the other. (iv) A figure which has more than two odd nodes cannot be described completely in one route; to which Listing added the corollary that a figure which has2n odd nodes, and no more, can be described completely inn separate routes. I now proceed to prove these theorems. First. The number of odd nodes in a closed network is even. Suppose the number of branches to beb. Therefore the number of hooks is 2b. Let kn be the number of nodes of thenth order. Since a node of thenth order is one at whichn branches meet, there aren hooks there. Also since the figure is closed,n cannot be less than2. ∴ 2k2 + 3k3 + 4k4 + · · · + nkn + · · · = 2b . Hence 3k3 + 5k5 + · · · is even. ∴ k3 + k5 + · · · is even. Second. A figure which has no odd node can be described unicur- sally in a re-entrant route. * Die Studien, Göttingen, 1847, part x. See also Tait on Listing’s Topologie, Philosophical Magazine, London, January, 1884, series 5, vol.xvii, pp. 30–46.

PG26839.B00163
[PDF page 162] 146 UNICURSAL PROBLEMS. [CH. VI Since the route is to be re-entrant it will make no difference where it commences. Suppose that we start from a nodeA. Every time our route takes us through a node we use up one hook in entering it and one in leaving it. There are no odd nodes, therefore the number of hooks at every node is even: hence, if we reach any node exceptA, we shall always find a hook which will take us into a branch previously untra- versed. Hence the route will take us finally to the nodeA from which we started. If there are more than two hooks atA, we can continue the route over one of the branches fromA previously untraversed, but in the same way as before we shall finally come back toA. It remains to show that we can arrange our route so as to make it cover all the branches. Suppose each branch of the network to be represented by a string with a hook at each end, and that at each node all the hooks there are fastened together. The number of hooks at each node is even, and if they are unfastened they can be re-coupled together in pairs, the arrangement of the pairs being immaterial. The whole network will then form one or more closed curves, since now each node consists merely of two ends hooked together. If this random coupling gives us one single curve then the proposi- tion is proved; for starting at any point we shall go along every branch and come back to the initial point. But if this random coupling pro- duces anywhere an isolated loop,L, then where it touches some other loop, M, say at the nodeP, unfasten the four hooks there (viz. two of the loop L and two of the loopM) and re-couple them in any other order: then the loopL will become a part of the loopM. In this way, by altering the couplings, we can transform gradually all the separate loops into parts of only one loop. For example, take the case of three isles,A, B, C, each connected with both the others by two bridges. The most unfavourable way of re- coupling the ends atA, B, C would be to makeABA, ACA, andBCB separate loops. The loopsABA and ACA are separate and touch atA; hence we should re-couple the hooks atA so as to combineABA and ACA into one loopABACA. Similarly, by re-arranging the couplings of the four hooks atB, we can combine the loopBCB with ABACA and thus make only one loop. I infer from Euler’s language that he had attempted to solve the problem of giving a practical rule which would enable one to describe such a figure unicursally without knowledge of its form, but that in this

PG26839.B00164
[PDF page 163] CH. VI] EULER’S PROBLEM. 147 B C A he was unsuccessful. He however added that any geometrical figure can be described completely in a single route provided each part of it is described twice and only twice, for, if we suppose that every branch is duplicated, there will be no odd nodes and the figure is unicursal. In this case any figure can be described completely without knowing its form: rules to effect this are given below. Third. A figure which has two and only two odd nodes can be described unicursally by a point which starts from one of the odd nodes and finishes at the other odd node. This at once reduces to the second theorem. LetA and Z be the two odd nodes. First, suppose that Z is not a free end. We can, of course, take a route fromA to Z; if we imagine the branches in this route to be eliminated, it will remove one hook fromA and make it even, will remove two hooks from every node intermediate betweenA and Z and therefore leave each of them even, and will remove one hook from Z and therefore will make it even. All the remaining network is now even: hence, by Euler’s second proposition, it can be described unicursally, and, if the route begins at Z, it will end at Z. Hence, if these two routes are taken in succession, the whole figure will be described unicursally, beginning atA and ending at Z. Second, if Z is a free end, then we must travel fromZ to some node, Y, at which more than two branches meet. Then a route fromA to Y which covers the whole figure exclusive of the path fromY to Z can be determined as before and must be finished by travelling fromY to Z. Fourth. A figure having 2n odd nodes, and no more, can be de- scribed completely in n separate routes. If any route starts at an odd node, and if it is continued until it reaches a node where no fresh path is open to it, this latter node must be an odd one. For every time we enter an even node there is necessarily

PG26839.B00165
[PDF page 164] 148 UNICURSAL PROBLEMS. [CH. VI a way out of it; and similarly every time we go through an odd node we use up one hook in entering and one hook in leaving, but whenever we reach it as the end of our route we use only one hook. If this route is suppressed there will remain a figure with2n − 2 odd nodes. Hence n such routes will leave one or more networks with only even nodes. But each of these must have some node common to one of the routes already taken and therefore can be described as a part of that route. Hence the complete passage will require n and not more thann routes. It follows, as stated by Euler, that, if there are more than two odd nodes, the figure cannot be traversed completely in one route. The Königsberg bridges lead to a network with four odd nodes; hence, by Euler’s fourth proposition, it cannot be described unicur- sally in a single journey, though it can be traversed completely in two separate routes. The first and second diagrams figured below contain only even nodes, and therefore each of them can be described unicursally. The first of these—a re-entrant pentagon—was one of the Pythagorean sym- bols. The other is the so-called sign-manual of Mohammed, said to have been originally traced in the sand by the point of his scimetar with- out taking the scimetar off the ground or retracing any part of the figure—which, as it contains only even nodes, is possible. The third diagram is taken from Tait’s article: it contains only two odd nodes, and therefore can be described unicursally if we start from one of them and finish at the other. As other examples I may note that the geometrical figure formed by taking a (2n + 1)gon and joining every angular point with every other angular point is unicursal. On the other hand a chess-board, divided as usual by straight lines into64 cells, has 28 odd nodes and

PG26839.B00166
[PDF page 165] CH. VI] MAZES AND LABYRINTHS.. 149 53 even nodes: hence it would require14 separate pen-strokes to trace out all the boundaries without going over any more than once. Again, the diagram on page 102 has20 odd nodes and therefore would require 10 separate pen-strokes to trace it out. It is well known that a curve which has as many nodes as is con- sistent with its degree is unicursal. Mazes. Everyone has read of the labyrinth of Minos in Crete and of Rosamund’s Bower. A few modern mazes exist here and there— notably one, which is a very poor specimen of its kind, at Hampton Court—and in one of these, or at any rate on a drawing of one, most of us have threaded our way to the interior. I proceed now to consider the manner in which any such construction may be completely traversed even by one who is ignorant of its plan. The theory of the description of mazes is included in Euler’s theo- rems given above. The paths in the maze are what previously we have termed branches, and the places where two or more paths meet are nodes. The entrance to the maze, the end of a blind alley, and the centre of the maze are free ends and therefore odd nodes. If the only odd nodes are the entrance to the maze and the centre of it–which will necessitate the absence of all blind alleys–the maze can be described unicursally. This follows from Euler’s third proposition. Again, no matter how many odd nodes there may be in a maze, we can always find a route which will take us from the entrance to the centre without retracing our steps, though such a route will take us through only a part of the maze. But in neither of the cases mentioned in this paragraph can the route be determined without a plan of the maze. A plan is not necessary, however, if we make use of Euler’s sugges- tion, and suppose that every path in the maze is duplicated. In this case we can give definite rules for the complete description of the whole of any maze, even if we are entirely ignorant of its plan. Of course to walk twice over every path in a labyrinth is not the shortest way of arriving at the centre, but, if it is performed correctly, the whole maze is traversed, the arrival at the centre at some point in the course of the route is certain, and it is impossible to lose one’s way. I need hardly explain why the complete description of such a du- plicated maze is possible, for now every node is even, and hence, by Euler’s second proposition, if we begin at the entrance we can traverse

PG26839.B00167
[PDF page 166] 150 UNICURSAL PROBLEMS. [CH. VI the whole maze; in so doing we shall at some point arrive at the cen- tre, and finally shall emerge at the point from which we started. This description will require us to go over every path in the maze twice, and as a matter of fact the two passages along any path will be always made in opposite directions. If a maze is traced on paper, the way to the centre is generally obvious, but in an actual labyrinth it is not so easy to find the correct route unless the plan is known. In order to make sure of describing a maze without knowing its plan it is necessary to have some means of marking the paths which we traverse and the direction in which we have traversed them—for example, by drawing an arrow at the entrance and end of every path traversed, or better perhaps by marking the wall on the right-hand side, in which case a path may not be entered when there is a mark on each side of it. If we can do this, and if when a node is reached, we take, if it be possible, some path not previously used, or, if no other path is available, we enter on a path already traversed once only, we shall completely traverse any maze in two dimensions*. Of course a path must not be traversed twice in the same direction, a path already traversed twice (namely, once in each direction) must not be entered, and at the end of a blind alley it is necessary to turn back along the path by which it was reached. I think most people would understand by a maze a series of inter- lacing paths through which some route can be obtained leading to a space or building at the centre of the maze. I believe that few, if any, mazes of this type existed in classical or medieval times. One class of what the ancients called mazes or labyrinths seems to have comprised any complicated building with numerous vaults and passages†. Such a building might be termed a labyrinth, but it is not what is usually understood by the word. The above rules would enable anyone to traverse the whole of any structure of this kind. I do not know if there are any accounts or descriptions of Rosamund’s Bower * See Le problème des labyrinthesby G. Tarry,Nouvelles Annales de mathémat- iques, May, 1895, series 3, vol.xiv. † For instance, see the descriptions of the labyrinth at Lake Moeris given by Herodotus, bk. ii, c. 148; Strabo, bk. xvii, c. 1, art. 37; Diodorus, bk. i, cc. 61, 66; and Pliny, Hist. Nat., bk. xxxvi, c. 13, arts. 84–89. On these and other references see A. Wiedemann,Herodots zweites Buch, Leipzig, 1890, p. 522et seq. See also Virgil, Aeneid, bk. v, c. v, 588; Ovid, Met., bk. viii, c. 5, 159; Strabo, bk. viii, c. 6.

PG26839.B00168
[PDF page 167] CH. VI] MAZES AND LABYRINTHS.. 151 other than those by Drayton, Bromton, and Knyghton: in the opinion of some, these imply that the bower was merely a house, the passages in which were confusing and ill-arranged. Anotherclassofancientmazesconsistedofatortuouspathconfined to a small area of ground and leading to a place or shrine in the centre*. This is a maze in which there is no chance of taking a wrong turning; but, as the whole area can be occupied by the windings of one path, the distance to be traversed from the entrance to the centre may be considerable, even though the piece of ground covered by the maze is but small. The traditional form of the labyrinth constructed for the Minotaur is a specimen of this class. It was delineated on the reverses of the coins of Cnossus, specimens of which are not uncommon; one form of it is indicated in the accompanying diagram (figure i). The design really is the same as that drawn in figure ii, as can be easily seen by bending round a circle the rectangular figure there given. Mr Inwards has suggested†that this design on the coins of Cnossus may be a survival from that on a token given by the priests as a clue to Figure i. Figure ii. the right path in the labyrinth there. Taking the circular form of the design shown above he supposed each circular wall to be replaced by two equidistant walls separated by a path, and thus obtained a maze to which the original design would serve as the key. The route thus indicated may be at once obtained by noticing that when a node is reached (i.e. a point where there is a choice of paths) the path to be * On ancient and medieval labyrinths—particularly of this kind—see an article by Mr E. Trollope inThe Archaeological Journal, 1858, vol.xv, pp. 216–235, from which much of the historical information given above is derived † Knowledge, London, October, 1892.

PG26839.B00169
[PDF page 168] 152 UNICURSAL PROBLEMS. [CH. VI taken is that which is next but one to that by which the node was approached. This maze may be also threaded by the simple rule of always following the wall on the right-hand side or always that on the left-hand side. The labyrinth may be somewhat improved by erecting a few additional barriers, without affecting the applicability of the above rules, but it cannot be made really difficult. This makes a pretty toy, but though the conjecture on which it is founded is ingenious it must be regarded as exceedingly improbable. Another suggestion is that the curved line on the reverse of the coins indicated the form of the rope held by those taking part in some rhythmic dance; while others consider that the form was gradually evolved from the widely prevalent svastika. Copies of the maze of Cnossus were frequently engraved on Greek and Roman gems; similar but more elaborate designs are found in nu- merous Roman mosaic pavements*. A copy of the Cretan labyrinth was embroidered on many of the state robes of the later Emperors, and, apparently thence, was copied on to the walls and floors of vari- ous churches†. At a later time in Italy and in France these mural and pavement decorations were developed into scrolls of great complexity, but consisting, as far as I know, always of a single line. Some of the best specimens now extant are on the walls of the cathedrals at Lucca, Aix in Provence, and Poitiers; and on the floors of the churches of Santa Maria in Trastevere at Rome, San Vitale at Ravenna, Notre Dame at St Omer, and the cathedral at Chartres. It is possible that they were usedtorepresentthejourneythroughlifeasakindofpilgrim’sprogress. In England these mazes were usually, perhaps always, cut in the turf adjacent to some religious house or hermitage: and there are some slight reasons for thinking that, when traversed as a religious exercise, a pater orave hadtoberepeatedateveryturning. AftertheRenaissance, such labyrinths were frequently termed Troy-towns or Julian’s bowers. Some of the best specimens, which are still extant, are those at Rockliff Marshes, Cumberland; Asenby, Yorkshire; Alkborough, Lincolnshire; Wing, Rutlandshire; Boughton-Green, Northamptonshire; Comberton, Cambridgeshire; Saffron Walden, Essex; and Chilcombe, near Win- chester. The modern maze seems to have been introduced—probably from Italy—during the Renaissance, and many of the palaces and large * See ex. gr.Breton’sPompeia, p. 303. † Ozanam, Graphia aureae urbis Romae, pp. 92, 178.

PG26839.B00170
[PDF page 169] CH. VI] MAZES AND LABYRINTHS.. 153 houses built in England during the Tudor and the Stuart periods had labyrinths attached to them. Those adjoining the royal palaces at Southwark, Greenwich, and Hampton Court were particularly well known from their vicinity to the capital. The last of these was designed by London and Wise in 1690, for William III, who had a fancy for such conceits: a plan of it is given in various guide-books. For the majority Maze at Hampton Court. of the sight-seers who enter, it is sufficiently elaborate; but it is an indifferent construction, for it can be described completely by always following the hedge on one side (either the right hand or the left hand), and no node is of an order higher than three. Unless at some point the route to the centre forks and subsequently the two forks reunite, forming a loop in which the centre of the maze is situated, the centre can be reached by the rule just given, namely, by following the wall on one side—either on the right hand or on the left hand. No labyrinth is worthy of the name of a puzzle which can be threaded in this way. Assuming that the path forks as described above, the more numerous the nodes and the higher their order the more difficult will be the maze, and the difficulty might be increased considerably by using bridges and tunnels so as to construct a labyrinth in three dimensions. In an ordinary garden and on a small piece of ground, often of an inconvenient shape, it is not easy to make a maze which fulfils these conditions. Here on the following page is a plan of one which I put up in my own garden on a plot of ground which would not allow of more than36 by 23 paths, but it will be noticed that none of the nodes are of a high order.

PG26839.B00171
[PDF page 170] 154 UNICURSAL PROBLEMS. [CH. VI Geometrical Trees. Euler’s original investigations were con- fined to a closed network. In the problem of the maze it was assumed that there might be any number of blind alleys in it, the ends of which formed free nodes. We may now progress one step farther, and sup- pose that the network or closed part of the figure diminishes to a point. This last arrangement is known as atree. The number of unicursal descriptions necessary to completely describe a tree is called thebase of the ramification. We can illustrate the possible form of these trees by rods, having a hook at each end. Starting with one such rod, we can attach at either end one or more similar rods. Again, on any free hook we can attach one or more similar rods, and so on. Every free hook, and also every point where two or more rods meet, are what hitherto we have called nodes. The rods are what hitherto we have termed branches or paths. The theory of trees—which already plays a somewhat important part in certain branches of modern analysis, and possibly may contain the key to certain chemical and biological theories—originated in a memoir by Cayley*, written in 1856. The discussion of the theory has * Philosophical Magazine, March, 1857, series4, vol.xiii, pp.172–176; orCollected Works, Cambridge, 1890, vol.iii, no. 203, pp. 242–346: see also the paper on double partitions, Philosophical Magazine, November, 1860, series 4, vol.xx, pp. 337–341. On the number of trees with a given number of nodes, see the

PG26839.B00172
[PDF page 171] CH. VI] THE HAMILTONIAN GAME. 155 been analytical rather than geometrical. I content myself with noting the following results. The number of trees with n given nodes is nn−2. If An is the number of trees withn branches, and Bn the number of trees withn free branches which are bifurcations at least, then (1 − x)−1(1 − x2)−A1(1 − x3)−A2 · · · = 1 + A1x + A2x2 + A3x3 + · · · , (1 − x)−1(1 − x2)−B2(1 − x3)−B3 · · · = 1 + x + 2B2x2 + 2B3x3 + · · · . Using these formulae we can find successively the values ofA1, A2, . . ., and B1, B2, . . .. The values of An when n = 2, 3, 4, 5, 6, 7, are 2, 4, 9, 20, 48, 115; and of Bn are 1, 2, 5, 12, 33, 90. I turn next to consider some problems where it is desired to find a route which will pass once and only once through each node of a given geometrical figure. This is the reciprocal of the problem treated in the first part of this chapter, and is a far more difficult question. I am not aware that the general theory has been considered by mathematicians, though two special cases—namely, theHamiltonian (or Icosian)Game and theKnight’s Path on a Chess-Board—have been treated in some detail; and I confine myself to a discussion of these. The Hamiltonian Game. The Hamiltonian Game consists in the determination of a route along the edges of a regular dodecahedron which will pass once and only once through every angular point. Sir William Hamilton*, who invented this game—if game is the right term for it—denoted the twenty angular points on the solid by letters which stand for various towns. The thirty edges constitute the only possible paths. The inconvenience of using a solid is considerable, and the dodecahedron may be represented conveniently in perspective by a flat board marked as shown in the first of the annexed diagrams. The Quarterly Journal of Mathematics, London, 1889, vol.xxiii, pp. 376–378. The connection with chemistry was first pointed out in Cayley’s paper on isomers, Philosophical Magazine, June, 1874, series 4, vol.xl vii, pp. 444–447, and was treated more fully in his report on trees to the British Association in 1875, Reports, pp. 257–305. * See Quarterly Journal of Mathematics, London, 1862, vol.v, p. 305; orPhilo- sophical Magazine, January, 1884, series 5, vol.xvii, p. 42; also Lucas, vol.ii, part vii.
