Leonhard Euler, “Solution of a problem in the geometry of position”

Latine

{128}

SOLUTION OF A PROBLEM

IN THE

GEOMETRY OF POSITION.

BY

Leonhard Euler.

§1.

Besides that part of geometry which is concerned with quantities, and has at all times been studied with the greatest zeal, there is another part, still quite unknown, of which Leibnitz was the first to make mention and which he called geometria situs, the geometry of position. This part is defined by him as being concerned only with the determination of position, and with drawing out the properties of position; in which business quantities are not considered, nor is calculation with quantites employed. But what kinds of problem belong to this geometry of position, and what kind of method is suitable for solving them, is not adequately defined. So, since mention was recently made of a certain problem, which clearly had something to do with geometry, but was presented in such a way that it neither required the determination of quantities, nor did calculation with quantities help towards its solution, I did not hesitate to refer it to the geometry of position: especially because in its solution only position is considered; there is no need at all for [geometrical] calculation. Therefore I have decided to publish here my method that I have found for solving {129} problems of this kind, as a typical example of the geometry of position.

Figure 1 §2. This problem, then, which was described to me as quite well known, was as follows: At Königsberg in Prussia there is an island A called der Kneiphof, and the river around it is divided into two branches, as shown in the figure; and the branches of this river are crossed by seven bridges a, b, c, d, e, f, and g. The following question was now raised concerning these bridges: whether someone could arrange a walk in such a way as to travel over every bridge once and not more than once. Some people (I was told) deny that this is possible, and others doubt it; but nobody asserts it. From this I set myself the following quite general problem: whatever the form of the river and its distribution into branches, and whatever the number of bridges, to find whether it is possible for each bridge to be crossed only once, or not.

§3. As far as the Königsberg problem of seven bridges is concerned, it could be solved by a complete enumeration of all the walks that could be planned; for from these it would be known whether any walk was a solution, or none. But, because of the large number of combinations, this way of solving it would be difficult and laborious, and in other questions with many more bridges it could not be carried out at all. By this method moreover, if the working is carried out to the end, many things are found which were not looked for; it is this no doubt that causes so much difficulty [1]. Therefore, dismissing this method, I looked for another, which would be no more {130} generous than to show whether such a walk could be planned or not; for I suspected that such a method would be much simpler [2].

§4. Now my whole method is based on a suitable way of denoting individual crossings of bridges, in which I use capital letters A, B, C, D applied to the individual regions that are separated by the river. Thus if someone crosses from region A into region B by bridge a or b, I denote this crossing by the letters AB, of which the first shows the region from which the traveller left, and the second gives the region in which he arrives after crossing the bridge. If the traveller next goes out of region B into region D by bridge f, this crossing is represented by the letters BD; but these two crossings AB and BD, if made in succession, I denote by only three letters ABD, for the middle one B denotes both the region in which he arrived on the first crossing, and the region from which he left on the second crossing.

§5. Similarly, if the traveller continues from region D into region C by bridge g, these three crossings, made in succession, I shall denote by the four letters ABDC. For from these four letters ABDC it will be understood that the traveller, who was at first in region A, has crossed to region B, from here has continued into region D, and from here has continued further into C: and since these regions are separated from each other by rivers, the traveller has necessarily crossed three bridges. Thus successive crossings by four bridges will be denoted by five letters; and if the traveller goes across any number of bridges, his journey will be denoted by a number of letters which is one {131} greater than the number of bridges. So then a crossing over seven bridges requires eight letters to represent it.

§6. In this notation I do not take account of the bridges by which the crossing is made, but if the same crossing from one region to another can be made by several bridges, it is just the same whichever one he crosses by, as long as he arrives in the designated region. From which it is understood that, if a walk across the seven bridges of the figure can be so arranged that each is crossed once and none twice, this walk can be represented by eight letters, and that those letters must be so arranged that the letters A and B occur together twice, for there are two bridges a and b joining these two regions A and B; similarly the letters A and C must also occur together twice in that series of eight letters; next the letters A and D will occur together once; and similarly it is necessary that the letters B and D, as also C and D, shall occur together once.

§7. The question therefore reduces to that of forming from the four letters A, B, C, D a series of eight letters, in which all those two-letter sequences shall occur the prescribed number of times. But before we begin working towards such an arrangement, we shall do well check whether these letters can be arranged in such a way or not. For if it can be proved that there is no way to make such an arrangement, all labour put in towards doing so will be wasted. Therefore I have found a rule, by the help of which it is easy to see, both for this question and {132} all similar ones, whether such an arrangement of letters can occur.

§8. Figure 2 In order to find such a rule I consider a single region A, into which lead any number of bridges a, b, c, d etc. Of these bridges I first consider a single one a, which leads to the region A; if now the traveller crosses by this bridge he must either have been in region A before crossing or arrive in region A after crossing; so that the above-established notation for crossings requires the letter A to occur once. If, say, three bridges a, b, c lead into region A, and the traveller crosses by all three, then in the record of his travels the letter A will occur twice, whether he starts his walk at A or not. In the same way if five bridges lead into A, in the record of crossing them all the letter A must occur three times. And if the number of bridges is any odd number, then if it is increased by one, its half will give the number of places in which the letter A must occur.

Figure 1 §9. In the case therefore of the bridges that have to be crossed at Königsberg, since five bridges a, b, c, d, e lead into the island A it is necessary that in the record of crossing by these bridges the letter A shall occur three times. Next the letter B, since three bridges lead into region B, must occur twice, similarly the letter D must occur twice, and again the letter C twice. Therefore in the series of eight letters by which the crossing of the seven bridges would have to be recorded, the letter A would have to be present three times, and each of the letters {133} B, C, D twice; which in a series of eight letters cannot be done at all. From which it is clear that such a crossing of the seven Königsberg bridges cannot be achieved.

§10. In a similar way it is possible to decide for every other set of bridges, provided the number of bridges that leads into any region is odd, whether the crossing can be made once across every bridge. For if it turns out that the sum of all the places, in which the separate letters must occur, equals the number of bridges plus one, then such a crossing can be made; but if, as happens in our example, the sum of all the places is greater than the number of bridges plus one, then such a crossing can by no means be achieved. And the rule I have given, for finding the number of places A from the number of bridges leading into A, is equally valid whether all the bridges lead from one region B (as shown in the figure) Figure 2 or from several; for I only consider the region A and inquire in how many places the letter A has to occur.

§11. If now the number of bridges leading into region A is even, then as regards crossing them once each we have to take note of whether the traveller sets off from region A or not. For if two bridges lead into A, and the traveller sets off from A, then the letter A must occur twice, as it is needed once to record leaving A by one bridge, and once to record coming back {134} into A by the other bridge. But if the traveller sets off from another region, then the letter A will occur only once, for one writing of it will record both the entry into A and the exit, according to my way of recording such walks.

§12. Now let four bridges lead into region A, and let the traveller set out from A; then in the record of the whole walk the letter A will have to occur three times, if he crosses each of them once. But if he starts walking from another region, then the letter A will occur exactly twice. If six bridges lead into region A then the letter A, if the journey starts from A, will occur four times; but if the traveller does not start from A, then it will have to occur only three times. Whence in general if the number of bridges is even, then its half gives the number of places in which the letter A must occur, if A is not taken as the starting-point; but its half plus one will give the number of places in which the letter A must occur, if the starting-point of the walk is in region A itself.

§13. Now since in such a walk the start can be made in only one region [3], I accordingly define, from the number of bridges that lead into any region, the number of times that a letter denoting a region must occur, in the following way: I shall take half of one more than the number of bridges, if the number of bridges is odd; and half the number of bridges itself, if it is even. Then if the total number of places equals the number of bridges plus one, the desired crossing will succeed, but the beginning must be taken from a region into which an odd number {135} of bridges leads. But if the total number of places is one less than the number of bridges plus one, the crossing will succeed beginning from a region into which an even number of bridges leads, because in this way the number of places needs to be increased by one.

§14. Given therefore any arrangement of waters and bridges, in order to find out whether someone can cross each bridge exactly once, I set out the working in the following way. Firstly I denote by letters A, B, C etc. the regions separated from each other by water. Secondly I take the total number of bridges, increase it by one, and place the result at the top of the working that follows. Thirdly, having written the letters A, B, C, etc. one below another, I write next to each the number of bridges leading to that region. Fourthly, I mark with an asterisk those letters that have even numbers written next to them. Fifthly, next to each number I write half of each of these even numbers, but half of one more than each of the odd numbers. Sixthly, I cast these last-written numbers into a single sum, and if this sum is one less than or equal to the number prefixed above (which is one more than the total number of bridges), then I conclude that the desired crossing can be made. But one must keep in mind that if the sum so found is one less than the number placed at the start, then the walk has to be started in a region marked with an asterisk, and on the other hand from a region not so marked if the sum is equal to the number written at the top. Therefore, in the case of Königsberg, I set out the working as follows: {136}

Therefore, since the result is more than 8, such a crossing cannot be made at all.

Figure 3 §15. Let two islands A and B be surrounded by water, and let four rivers communicate with this water, as shown in the figure. Further, let fifteen bridges a, b, c, d, etc. be thrown across the rivers and the water surrounding the islands, and suppose it is asked whether someone can plan a walk in such a way that he crosses all the bridges, but none more than once. I therefore first label all the regions that are separated from one another by water with the letters A, B, C, D, E, F, from which it follows that there are six regions. Next, I increase 15, the number of bridges, by one and write the sum 16 at the top of the following working.

{137} Thirdly, I write the letters A, B, C, etc. in order beneath, and by each I put the number of bridges that lead to that region: thus to A lead eight bridges, to B four etc. Fourthly, I mark with an asterisk the letters that have an even number next to them. Fifthly, in the third column I write the halves of the even numbers, while to the odd numbers I add one and then write the halves. Sixthly, I add together the numbers of the third column, and obtain the sum 16. Since this is equal to the number 16 placed at the top, it follows that the crossing can be made in the desired way, provided that the walk starts either from from region D or from E, since these are not marked with an asterisk. Indeed, the walk can be done thus: EaFbBcFdAeFfCgAhCiDkAmEnApBqElD, where between the capital letters I have also placed the bridges by which the crossing is made.

§16. By this means it will therefore be easy to decide, in the most complicated case, whether a crossing by each bridge once only can be made or not. However, I shall give a way of deciding the same thing which is much simpler still, and can be derived from the former without difficulty, once I have set down the following observations. First then I note that the numbers of bridges written next to the respective letters A, B, C when added together are twice the total number of bridges. The reason is that in this calculation, in which all the bridges leading into a given region are counted, each bridge is counted twice; for any bridge is counted once for each of the two regions that it joins.

{138} §17. It follows from this observation that the sum of all bridges that lead into the respective regions is an even number, since its half is equal to the number of bridges. Therefore it cannot happen that, among the numbers of bridges leading into any region, there is exactly one odd number, nor again that there are three odd numbers, nor five, etc. So that if any of the bridge counts written next to the letters A, B, C, etc. are odd, the number of these is necessarily even: thus in the Königsberg example there were four odd bridge counts, written next to the letters of regions A, B, C, D, as can be seen in §. 14; and in the previous example §. 15 there are exactly two odd numbers, written next to the letters D and E.

§18. Since the sum of all numbers adjoined to the letters A, B, C etc. equals twice the number of bridges, it is clear that this number increased by 2 and then divided by 2 gives the number placed at the top of the working. If therefore all the numbers written next to the letters A, B, C, D etc. are even, and half of each is taken in order to obtain the numbers of the third column, the sum of the latter numbers will be one less than the number at the top. Therefore in these cases the crossing by all the bridges can always be made. For in whatever region the walk is started, that region will have an even number of bridges leading to it, as required. Thus in the Königsberg example it is possible for someone to cross all the bridges twice, since any bridge will be (as it were) split into two, and the number of bridges leading into any region will be even.

{139} §19. Further, if exactly two of the numbers written next to the letters A, B, C etc. are odd, but the rest are even, then the desired crossing will always succeed, provided the walk starts from a region with an odd number of bridges leading to it. For if the even numbers, and also the odd numbers plus one, are halved as laid down above, the sum of these halves will be one more than the number of bridges, and therefore equal to the number at the top. And from this it can further be seen that if there are four or six or eight etc. odd numbers in the second column, then the sum of the numbers in the third column will be greater than the number at the top, exceeding it by one or two or three etc., and for this reason the crossing cannot be done.

§20. Therefore in any given case it will be very easy to decide straightaway whether a crossing by each bridge once only can be planned or not, with the help of the following rule. If there are more than two regions with an odd number of bridges leading into them, then it can safely be stated that there is no such crossing. And if there are exactly two regions with an odd number of bridges leading into them, then the crossing can be done, provided the walk is started in one of these two regions. Finally, if there is no region at all with an odd number of bridges leading to into it, then the crossing can be planned in the desired way, and the start of the walking can be placed in any region. Therefore the rule just given fully satisfies the statement of the problem.

{140} §21. But when it has been found that such a crossing can be arranged, the question remains how the walk is to be carried out. For this I use the following rule: in imagination, let the bridges that lead from one region to another be removed in pairs as many times as possible, by which the number of bridges will in most cases be greatly reduced; then let a walk be planned across the remaining bridges, which is easily done; then the bridges that were imagined as removed will not much disturb the walk so found, as will at once be seen on very little consideration; nor do I think it necessary to give more rules for arranging the walks.