CHAPTER VIII.

tJNICURSAL PROBLEMS.
I propose to consider in this chapter some problems which arise out of the theory of unicursal curves. I shall commence with Fillers Problem and Theorems, and shall apply ^he results briefly to the theories of Mazes and Oeometrical Trees. The reciprocal unicursal problem of the Hamilton Game will 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 Konigsberg 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 below and includes the island of Kneiphof. In the eighteenth century 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 Konigsberg, but discussed the general problem of any number of islands con- nected in any way by bridges. It is evident that the question
" ' Solutio problematis ad Geometriam situs pertinentis,' Gommentarii Academiae Scientiarum Petropolitanae for 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.
CH. VIIl]
UNICURSAL PROBLEMS
171
will not be affected if 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 Kdnigsberg problem this figure is of the shape indicated below, the areas being represented by the points A^ B, G, D, and the bridges being represented by the lines I, m, n, p, q, r, s.
Euler's problem consists therefore in finding whether a given geometrical 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 determine how many strokes are neces- sary 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 repre- sented 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
172 UNICURSAL PROBLEMS [CH. VIII
in the propositions proved by Listing in his Topologie*. 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 a free node or a free end. A node at which an even number of branches meet is an even node : evidently the presence of a node of the second order is immaterial. A node at which an odd number of branches meet is an odd 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 con- secutive order and so that no branch is traversed twice. A closed route terminates at a point from which it started. A figure is described unicursally when the whole of it is traversed in one route.
The following are Euler's results, (i) In a closed net- work the number 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 nodes 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 com- pletely in one route; to which Listing added the corollary that a figure which has 2n odd nodes, and no more, can be described completely in n separate routes. I now proceed to prove these theorems.
* Die Studien, Gottingen, 1847, part x. See also Tait on ^Listing's Topologie,^ Philosophical Magazine, London, January, 1884, series 5, vol. xvii, pp. 30 — 46; and Collected Scientific Papers, Cambridge, vol. n, 1900, pp. 85 — 98. The problem was discussed by J. C. Wilson in his Traversing of Geometrical Figures, Oxford, 1905.
y
CH. VIIl] UNICURSAL PROBLEMS 173
First, The number of odd nodes in a closed network is even.
Suppose the number of branches to be b. Therefore the number of hooks is 26. Let kn be the number of nodes of the ?ith order. Since a node of the nth. order is one at which n branches meet, there are n hooks there. Also since the figure is closed, n cannot be less than 2.
,*. 2k2 + •3^'3 + 4Ar4 + . . . + nkn + . .. = 26.
Hence Sk^ + bk^ + ... is even,
/. Arg + ^5 + ... is even.
Second. A figure which has no odd node can he described unicursally in a re-entrant route.
Since the route is to be re-entrant it will make no difference where it commences. Suppose that we start from a node A. 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 except A, we shall always find a hook which will take us into a branch previously untraversed. Hence the route will take us finally to the node A from which we started. If there are more than two hooks at ^, we can continue the route over one of the branches from A previously untraversed, but in the same way as before we shall finally come back to A.
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 proposition is proved; for starting at any point we shall go along eveiy branch and come back to the initial point. But
174 UNICURSAL PROBLEMS [CH. VIII
if this random coupling produces anywhere an isolated loop, i, then where it touches some other loop, M, say at the node P, unfasten the four hooks there (viz. two of the loop L and two of the loop M) and re-couple them in any other order: then the loop L will become a part of the loop M, 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, (7, each connected with both the others by two bridges. The most unfavourable way of re-coupling the ends at A, B, C would be to make ABA, AC A, and BOB separate loops. The loops ABA and AC A are separate and touch at A; hence we should re-couple the hooks at A so as to combine ABA and AC A into
A
one loop ABACA. Similarly, by re-arranging the couplings of the four hooks at B, we can combine the loop BCB 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 he was unsuccessful. He however added that any geometrical figure can be de- scribed completely in a single route provided each part of it is described twice and only twice, for, if we suppose that every iM-anch is duplicated, there will be no odd nodes and the figure is unicursal. In this case any figure can be described com- pletely without knowing its form : rules to effect this are given below.
Third. A figure which has two and only two odd nodes can he described unicursally hy a point which starts from one of the, odd nodes and finishes at the other odd node.
CH. Vlll] UNICURSAL PROBLEMS 175
This at once reduces to the second theorem. Let A and Z be the two odd nodes. First, suppose that Z is not a free end. We can, of course, take a route from A to Z; if we imagine the branches in this route to be eliminated, it will remove one hook from A and make it even, will remove two hooks from every node intermediate between A 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, be- ginning at A and ending at Z. Second, if Z is a free end, then we must travel from Z to some node, Y, at which more than two branches meet. Then a route from A to Y which covers the whole figure exclusive of the path from Y to Z can be determined as before and must be finished by travelling from Y to Z.
Fourth. A figure having 2n odd nodes, and no more, can he described completely in n separate routes, n being a positive number.
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 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 with 2n — 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 com- plete passage will require n and not more than n 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.
176
UMICURSAL PROBLEMS
[CH. VIII
The Konigsberg bridges lead to a network with four odd nodes; hence, by Euler's fourth proposition, it cannot be described unicursally 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 uni- cursally. The first of these is a regular re-entrant pentagon ; the second is the so-called sign-manual of Mohammed, said to have been originally traced in the sand by the point of his scimetar without taking it off the ground or retracing any part of the figure — which, as it contains only even nodes, is possible. The third diagram is taken fi:om 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.
^4 ^^7
The re-entrant pentagon, figured above, has some interest from having been used by the Pythagoreans as a sign — known as the triple triangle or pentagram star — by which they could recognize one another. It was considered symbolical of health, and probably the angles were denoted by the letters of the word vyUta, the diphthong et being replaced by a 6. lamblichus, who is our authority for this, tells us that a certain Pythagorean, when travelling, fell ill at a roadside inn where he had put up for the night ; he was poor and sick, but the landlord, who was a kind-hearted fellow, nursed him carefully and spared no trouble or expense to relieve his pains. However, in spite of all efforts, the student got worse. Feeling that he was djdng and unable to make the landlord any pecuniary recompense, he asked for a board on which he inscribed the pentagram star; this he gave to his host, begging him to hang it up outside so that all passers by might see it, and assuring him that the result
CH. VIII] UNICURSAL PROBLEMS 177
would recompense him for his charity. The scholar died and was honourably buried, and the board was duly exposed. After a considerable time had elapsed, a traveller one day riding by saw the sacred symbol ; dismounting, he entered the inn, and after hearing the story, handsomely remunerated the landlord. Such is the anecdote, which if not true is at least well found.
As another example of a unicursal diagram I may mention the geometrical figure formed by taking a (2n + l)gon and joining every angular point to every other angular point. The edges of an octahedron also form a unicursal figure. On the other hand a chess-board, divided as usual by straight lines into 64 cells, has 28 odd nodes: hence it would require 14 separate pen-strokes to trace out all the boundaries without going over any more than once. Again, the diagram on page 117 has 20 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 consistent with its degree is unicursal.
I turn next to discuss in how many ways we can describe a unicursal figure, all of whose nodes are even*.
Let us consider first how the problem is affected by a path which starts from a node A of order 2n and returns to it, forming a closed loop L. If this loop were suppressed we should have a figure with all its nodes even, the node A being now of the order 2(w— 1). Suppose the original figure can be described in N ways, and the reduced figure in N' ways. Then each of these N' routes passes (n— 1) times through A, and in any of these passages we could describe the loop L in either sense as a part of the path. Hence N =2{n — l) N'.
Similarly if the node A on the original figure is ot the order 2 {u + l)y and there are I independent closed loops which start from and reiurn to -4, we shall have
N = 2hi (m -f- 1) (/z + 2) . . . (71 + ^ - 1 ) iV",
where N' is the number of routes by which the figure obtained by suppressing these I loops can be described.
* See G. Tarry, Association J^'ranc^aise pour VAvancement de$ Sciences, 1886, pp. 49 — 53.
B. R. 12
178 UNICURSAL PROBLEMS [CH. VIII
By the use of these results, we may reduce any unicursal figure to one in which there are no closed loops of the kind above described. Let us suppose that in this reduced figure there are k nodes. We can suppress one of these nodes, say A^ provided we replace the figure by two or more separate figures each of which has not more than k — 1 nodes. For suppose that the node A is of the order 2n, Then the 2/1 paths which meet at A may be coupled in n pairs in 1 . 3 . 5 ... (2?i— 1) ways and each pair will constitute either a path through J., or (in the special case where both members of the pair abut on another node B) a loop from A, This path or loop will form a portion of the route through A in which this pair of paths are concerned. Hence the number of ways of describing the original figure is equal to the sum of the number of ways of describing 1.3.5... (2n — 1) separate simpler figures.
It will be seen that the process consists in successively suppressing node after node. Applying this process continually we finally reduce the figure to a number of figures without loops and in each of which there are only two nodes. If in one of these figures these nodes are each of the order 2/1 it is easily seen that it can be described in 2 x {2n — 1)! ways.
We know that a figure with only two odd nodes, A and B, is unicursal if we start at A (or B) and finish at B (or A). Hence the number of ways in which it can be described uni- cursally will be the same as the number required to describe the figure obtained from it by joining A and B. For if we start at A it is obvious that at the B end of each of the routes which cover the figure we can proceed along BA to the node A whence we started.
This theory has been applied by Monsieur Tarry* to deter- mine the number of ways in which a set of dominoes, running up to even numbers, can be arranged. This example will serve to illustrate the general method.
A domino consists of a small rectangular slab, twice as long as it is broad, whose face is divided into two squares,
* See the second edition of the French Translation of this work, Paris, 1908, vol. u, pp. 253—263 ; see also Lucas, vol. iv, pp. 145—150.
CH. VIIl] UNICURSAL PROBLEMS 179
which are either blank or markod with 1, 2, 3... dots. An ordinary set contains 28 dominoes marked 6-6, 6-5, 6-4, 6-3, 6-2, 6-1, 6-0, 5-5, 5-4, 5-3, 5-2, 5-1, 5-0, 4-4, 4-3, 4-2, 4-li 4-0, 3-3, 3-2, 3-1, 3-0, 2-2, 2-1, 2-0, 1-1, 1-0, and 0-0. Dominoes are used in various games in most, if not all, of which the pieces are played so as to make a line such that consecutive squares of adjacent dominoes are marked alike. Thus if 6-3 is on the table the only dominoes which can be placed next to the 6 end are 6-6, 6-5, 6-4, 6-2, 6-1, or 6-0. Similarly the dominoes 3-5, 3-4, 3-3, 3-2, 3-1, or 3-0, can be placed next to the 3 end. Assuming that the doubles are played in due course, it is easy to see that such a set of dominoes will form a closed circuit*. We want to determine the number of ways in which such a line or circuit can be formed. Let us begin by considering the case of a set of 15 dominoes marked up to double-four. Of these 15 pieces, 5 are doubles. The remaining 10 dominoes may be represented by the sides and diagonals of a regular pentagon 01, 02, &c. The intersec- tions of the diagonals do not enter into the representation,
and accordingly are to be neglected. Omitting these from our consideration, the figure formed by the sides and diagonals of the pentagon has five even nodes, and therefore is unicursal. Any unicursal route (ex. gr. 0-1, 1-3, 3-0, 0-2, 2-3, 3-4, 4-1, 1-2, 2-4, 4-0) gives one way of arranging these 10 dominoes. Suppose there are a such routes. In any such route we may put each of the five doubles in any one of two positions {ex. gr.
* Hence if we remove one domino, say 5-4, we know that the line formed bj the rest of the dominoes must end on one side in a 5 and on the other in a 4.
12—2
180
UNICURSAL PROBLEMS
[CH. VIII
in the route given above the double-two can be put between 0-2 and 2-3 or between 1-2 and 2-4). Hence the total number of unicursal arrangements of the 15 dominoes is 2^a. If we arrange the dominoes in a straight line, then as we may begin with any of the 15 dominoes, the total number of arrangements is 15 . 2** . a.
We have next to find the number of unicursal routes of the pentagon delineated above in figure A. At the node 0 there are four paths which may be coupled in three pairs. If 0 1 and 0 2 are coupled, as also 0 3 and 0 4, we get figure B. If 0 1 and 0 3 are coupled, as also 0 2 and 0 4, we get figure G, If 0 1 and 0 4 are coupled, as also 0 2 and 0 3, we get figure D.
Figure B. Figure G. Figure D.
Let us denote the number of ways of describing figure B by 6, of describing figure C by c, and so on. The effect of suppressing the node 0 in the pentagon A is to give us three quadrilaterals, 5, C, B. And, in the above notation, we have a = h -\- c-\-d.
Take any one of these quadrilaterals, for instance D. We can suppress the node 1 in it by coupling the four paths which meet there in pairs. If we couple 1 2 with the upper of the paths 1 4, as also 1 3 with the lower of the paths 1 4, we get
Figure E. Figure F.
the figure E. If we couple 1 2 with the lower of the paths 1 4, as also 1 3 with the upper of the paths 1 4, we again get the figure E. If we couple 1 2 and 1 3, as also the two paths 1 4, we get the figure F. Then as above, d = 2e-^f. Similarly b = 2e +/, and c = 2e +/. Hence a — b-^c-rd = Qe-\-Sf,
CH. VIIl] UNICURSAL PROBLEMS 181
We proceed to consider each of the reduced figures E and F. First take E, and in it let us suppress the node 4. For simplicity of description, denote the two paths 0 2 by y8 and /9', and the two paths 4 3 by 7 and 7. Then we can couple /? and 7, as also 13' and 7', or we can couple /S and y, as also /9' and 7 : each of these couplings gives the figure 0. Or we can couple /3 and 13', as also 7 and 7 : this gives the figure H. Thus e=2g + h. Each of the figures G and H has only two nodes. Hence by the formulae given above, we have ^ = 2.3.2=12, and /i = 2.2.2 = 8. Therefore e = 2g+h = ^2. Next take the figure F. This has a loop at 4. If we suppress this
Q^- ^0
Figure G. Figure H. Figure J.
loop we get the figure J, and /= 2j. But the figure /, if we couple the two lines which meet at 4, is equivalent to the figure G. Thus /= 2j = 2g = 24. Introducing these results we have a = 6e + Sf= 192 + 72 = 264. And therefore iV=15.2^a=126720. This gives the number of possible arrangements in line of a set of 15 dominoes. In this solution we have treated an arrangement from right to left as distinct from one which goes from left to right : if these are treated as identical we must divide the result by 2. The number of arrangements in a closed ring is 2^a, that is 8448.
We have seen that this number of unicursal routes for a pentagon and its diagonals is 264. Similarly the number for a heptagon is h= 129976320. Hence the number of possible arrangements in line of the usual set of 28 dominoes, marked up to double-six, is 28 . 3^ h, which is equal to 7959229931520. The number of unicursal routes covering a polygon of nine sides is n = 2l^ 3^^ 5^ . 711 . 40787. Hence the number of possible arrangements in line of a set of 45 dominoes marked up to double-eight is 48 . 4^ . n*.
* These numerical conclusions have also been obtained by algebraical analysis : see M. Reiss, Aniiali di Matematica, Milan, 1871, vol. v, pp. 63—120.
182 UNICURSAL PROBLEMS [CH. VIII
Mazes. Everyone has read of the labyrinth of Minos in Crete and of Rosamund's Bower. A few modem mazes exist here and there — notably one, 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 people have at some time threaded their 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 theorems 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 suggestion, and suppose that every path in the maze is dupli- cated. 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 duplicated 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 the whole maze; in so doing we
CH. VIIl] UNICURSAL PROBLEMS 183
shall at some point arrive at the centre, 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.
Of the various practical rules for threading a maze those enunciated by M. Tremaux seem to be the simplest*. These I proceed to explain. For brevity I shall describe a path or a node as old or new according as it has been traversed once before or not at all. Then the rules are (i) whenever you come to a new node, take any path you like ; (ii) whenever you come by a new path to an old node or to the closed end of a blind alley, turn back along the path by which you have just come ; (iii) whenever you come by an old path to an old node, take a new path, if there is one, but if not, an old path ; (iv) of course a path traversed twice must not be entered. I should add that on emerging at any node then, of the various routes which are permitted by these rules, it will be convenient always to select that which lies next to one's right hand, or always that which lies next to one's left hand.
Few if any mazes of the type I have been considering (namely, a series of interlacing paths through which some route can be obtained leading to a space or building at the centre of the maze) 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
* Lucas, vol. I, part iii, p. 47 et aecj.
184
UNICURSAL PROBLEMS
[CH. VIII
vaults and passages*. Such a building might be termed a labyrinth, but it is not what is now 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 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.
Another class of ancient mazes consisted of a tortuous path confined to a small area of ground and leading to a tree or shrine in the centre f. 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.
Figure i.
Figure ii.
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
* 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 Buck, Leipzig, 1890, p. 522 et seq. See also Virgil, Aeneid, bk. v, c. v, 588; Ovid, Met., bk. viii, c. 5, 159; Strabo, bk. viii, c. 6.
t On ancient and medieval labyrinths — particularly of this kind — see an article by Mr E. Trollope in The Archaeological Journal, 1858, vol. xv, pp. 216 — 235, from which much of the historical information given above is derived.
CH. VIIl] UNICURSAL PROBLEMS 185
drawn in fisfiire 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 the right path in the labyrinth there. Taking the circular form of the design shown above he sup- posed 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 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 has no historical justification. 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 numerous Roman mosaic pavements f. A copy of the Cretan labyrinth was embroidered on many of the state robes of the later Emperors, and, ajoparently thence, was copied on to the walls and floors of various churches J. 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
* Knotoledge, London, October, 1892.
t See ex. gr. Breton's Pompeia, p. 303.
f Ozanam, Graphia aureae urbis Romae, pp. 92, 178.
186
UNICURSAL PROBLEMS
[CH. VIII
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 used to represent the journey through life as a kind of pilgrim's progress.
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 jpater or ave had to be repeated at every turning. After the Renaissance, such labyrinths were frequently termed Troy -Towns or Julian's Bowers. Some of the best specimens, which are still extant, or were so until recently, are those at Rockliff Marshes, Cumberland ; Asenby, Yorkshire ; Alkborough, Lincolnshire ; Wing, Rutlandshire ; Boughton-Green, Northamptonshire ; Comberton, Cambridge- shire; Saffron Walden, Essex; and Chilcombe, near Winchester.
Maze at Hampton Court.
The modern maze seems to have been introduced — probably from Italy — during the Renaissance, and many of the palaces and large houses built in England during the Tudor and the Stuart periods had labyrinths attached to them. Those adjoining the royal palaces at South wark, Greenwich, and Hampton Court were 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 of the sight-seers who enter, it is sufficiently
CH. VIIl]
UNICURSAL PROBLEMS
187
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 is a plan of one which I put up
in my own garden on a plot of ground which would not allow of more than 36 by 23 paths, but it will be noticed that none of the nodes are of a high order.
188 UNICURSAL PROBLEMS [CH. VIII
Geometrical Trees. Euler's original investigations were confined 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 further, and suppose that the network or closed part of the figure diminishes to a point. This last arrangement is known as a ti^ee. The number of unicursal descriptions necessary to completely describe a tree is called the base 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 been analytical rather than geometrical. I content myself with noting the following results.
The number of trees with n given nodes is n'^~'\ If An is the number of trees with n branches, and Bn the number of trees with n free branches which are bifurcations at least, then
{1 - x)-^ (1 - x^)-^^ (1 - a^)-^' = 1 + A,x + A^oc' + A,x^ + ..,,
(1 - x)-^ (l - x'')-^^- (1 - x')-^^ = l-\-x + 2B,x' + 2B,x' + ....
♦ Philosophical Magazine, March, 1857, series 4, vol. xra, pp. 172—176 ; or Collected Works, Cambridge, 1890, vol. iii, no. 203, pp. 242—216 : see also the paper on double partitions, Philosophical Magazine, November, 18G0, series 4, vol. XX, pp. 337 — 341. On the number of trees with a given number of nodes, see 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. xlvii, pp. 444—447, and was treated more fully in his report on trees to the British Association in 1875, Reports, pp. 257—305.
CH. VIIl]
UNICURSAL PROBLEMS
189
Using tliese formulae we can find successively the values of Ai,A2, ..., and Bi, B^, .... The values of An when n = 2, 3, 4, 5, 6, 7, are 2, 4, 9, 20, 48, 115; and of B^ 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, the Hamiltonian (or Icosian) Game and the Knight's Path on a Chess-Board — have been treated in some detail.
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 second and third diagrams will answer our purpose equally well and are easier to draw.
* See Quarterly Journal of Mathematics, London, 1862, voL v, p. 305 ; or Philosophical 2Iagazine, January, 1884, series 5. vol. xvii, p. 42; also Lucas, vol. II, part vii.
190 UNICURSAL PROBLEMS [CH. VIII
The first problem is to go "all round the world," that is, starting from any town, to go to every other town once and only once and to return to the initial town ; the order of the n towns to be first visited being assigned, where n is not greater than five.
Hamilton's rule for effecting this was given at the meeting in 1857 of the British Association at Dublin. ' At each angular point there are three and only three edges. Hence, if we approach a point by one edge, the only routes open to us are one to the right, denoted by r, and one to the left, denoted by I. It will be found that the operations indicated on opposite sides of the following equalities are equivalent,
lrH = rlry rl^r=lrl, lrH = r^, rl^r = l\
Also the operation Z^ or r^ brings us back to the initial point: we may represent this by the equations
To solve the problem for a figure having twenty angular points we must deduce a relation involving twenty successive operations, the total effect of which is equal to unity. By repeated use of the relation l^^rl^r we see that
1 = ^ = ^2^3 = {rl^r) I' = {rl^Y = K (^^'^) ^1"
= {rH^rlY = jr^ (rl^r) IrlY = {r^Mrl]\
Therefore {r'l'(riyY=l (i),
and similarly {Z V (Zr^j^ = 1 (ii).
Hence on a dodecahedron either of the operations
rrrlllrlrlrrrlllrlrl ... (i), II I r r r I r I r I I Irrrlrlr... (ii),
indicates a route which takes the traveller through every town. The arrangement is cyclical, and the route can be commenced at any point in the series of operations by transferring the proper number of letters from one end to the other. The point at which we begin is determined by the order of certain towns which is given initially.
CH. VIIl] UNICURSAL PROBLEMS 191
Thus, suppose that, we are told that we start from F and then successively go to B, A^ U, and T, and we want to find a route from T through all the remaining towns which will end at F. If we think of ourselves as coming into F from G, the path FB would be indicated by ^, but if we think of ourselves as coming into F from E, the path FB would be indicated by n The path from J5 to ^ is indicated by I, and so on. Hence our first paths are indicated either by lllr or hy rllr. The latter operation does not occur either in (i) or in (ii), and therefore does not fall within our solutions. The former operation may be regarded either as the 1st, 2nd, 3rd, and 4th steps of (ii), or as the 4th, 5th, 6th, and 7th steps of (i). Each of these leads to a route which satisfies the problem. These routes are
FBA UTPONGDEJKLMQRSHGF, and FBAVTSRKLMQPONGDEJHGF.
It is convenient to make a mark or to put down a counter at each corner as soon as it is reached, and this will prevent our passing through the same town twice.
A similar game may be played with other solids provided that at each angular point three and only three edges meet. Of such solids a tetrahedron and a cube are the simplest instances, but the reader can make for himself any number of plane figures representing such solids similar to those drawn on page 189. Some of these were indicated by Hamilton. In all such cases we must obtain from the formulae analogous to those given above cyclical relations like (i) or (ii) there given. The solution will then follow the lines indicated above. This method may be used to form a rule for describing any maze in which no node is of an order higher than three.
For solids having angular points where more than three edges meet — such as the octahedron where at each angular point four edges meet, or the icosahedron where at each angular point five edges meet — we should at each point have more than two routes open to us; hence (unless we suppress some of the edges) the symbolical notation would have to be
192 UNICURSAL PROBLEMS [CH. VITI
extended before it could be applied to these solids. I offer the suggestion to anyone who is desirous of inventing a new game.
Another and a very elegant solution of the Hamiltonian dodecahedron problem has been given by M. Hermary. It consists in unfolding the dodecahedron into its twelve penta- gons, each of which is attached to the preceding one by only one of its sides; but the solution is geometrical, and not directly applicable to more complicated solids.
Hamilton suggested as another problem to start from any town, to go to certain specified towns in an assigned order, then to go to every other town once and only once, and to end the journey at some given town. He also suggested the con- sideration of the way in which a certain number of towns should be blocked so that there was no passage through them, in order to produce certain effects. These problems have not, so far as I know, been subjected to mathematical analysis.
The problem of the knight's path on a chess-board is some- what similar in character to the Hamiltonian game. This I have already discussed in chapter VI.
193