Euler - A New Branch of Mathematics: Topology
Most of us tacitly assume that mathematics is a science dealing with the measurement of quantities. Indeed, the word "geometry", which is sometimes used synonymously with "mathematics," means "measurement of the earth." In the selection before us now, however, we see that mathematics includes a great deal more than measurement. Leonhard Euler, an eighteenth-century mathematician, shows us that "position" or "relative position" is a property that can be treated mathematically.Not only such questions as "are these two triangles of the same shape?" or "Is this number a factor of that number?" but also a question like "Is this point inside or outside of that figure?" are all mathematically significant.
If it seems strange that "relative position" should be a part of mathematics, a look at Euler's treatment will dispel any doubt. These "topological" matters are treated deductively and just as rigorously as matters of size and shape are treated by Euclid.Leonhard Euler: Solution of a Problem Belonging to the "Geometry of Position"
1. Beside that part of geometry which deals with quantities and which always is studied with the greatest care, Leibniz makes mention of another part. He was the first to do so, although it is almost unknown, and he called it geometria sirus (geometry of position). This part of geometry was stated by him to deal only with the determination of location and with eliciting the properties of location. In this business no regard is had to quantities nor is there any need for calculating quantities.However, this does not sufficiently define the sort of problems that belong to this geometry of position, nor what method is to be used in solving them. Therefore, since recently there has been made mention of a certain problem, which seems to pertain to geometry, but which is so constituted that it requires neither quantitative determination nor admits of quantitative solution through calculation, I have not had any doubt at all to refer it to the geometry of position, especially because in its solution only position comes under consideration, while calculation is of no use. Hence I have determined here to exhibit my method, which I have invented for solving problems of this kind, as an example of the geometry of position.
2. The problem, then, which I was told is quite well enough known, was the following: In Kiinigsberg in Prussia there is an island A, called the Kneipfhof, encircled by a river which divides into two arms, as can be seen from the figure: the branches are furnished with seven bridges, a, b, c, d, e, f, and g.Now the following question is asked concerning these bridges: Could someone follow a course so that he crosses each bridge once, and none more than once? I was told that some deny altogether that this is possible while others doubt it, but nobody asserts that it is possible. I formulated for myself the following general problem from this: whatever be the shape of the river and the distribution of its branches and whatever be the number of bridges, to find whether it is possible to cross all bridges once only, or not.
3. But since the problem of Kijnigsberg pertains to seven bridges, it could be solved by a complete enumeration of all the routes which can be taken; from this it would become clear whether some route satisfies the problem or not. But because of the great number of combinations this mode of solution is both too difficult and laborious and in other problems of more bridges cannot be employed at all. If this kind of method should be pursued to the end, many answers will be found to questions that were not asked; in this without doubt consists the cause of great difbculty. Wherefore having dismissed this method I have searched for another one which would not do anything more than show whether such a route can be found or not; for I suspected that such a method would be much simpler.
4. Now my whole method rests on a suitable way of designating each single crossing of the bridges; for this I use the capital letters A, B, C, D which describe each of the regions that are separated by the river. Thus, if someone goes from region A to region B, by either the bridge a or the bridge b, I denote this crossing by the letters AB. The f%st of these shows the region from which the traveler came, and the second gives the region into which he goes after crossing the bridge. Again, if a traveler should go from region B to region D by bridge f, this crossing is represented by the letters BD. Two successive crossings AB and BD I then denote by the three letters ABD, because the middle letter B designates both the region which he reached by the tist crossing and the region which he left by the second crossing.
5. Similarly, if the traveler should go on from region D to region C by the way of bridge g, I denote these three successive crossings by the four letters ABDC. From these four letters ABDC it will be understood that the traveler was fist in region A and crossed into region B, that from here he went on to region D and that from here he tinally proceeded to C. Since, however, these regions are separated from each other by the river, it is necessary that the walker crossed three bridges. Thus crossings that are undertaken by way of four successive bridges are denoted by five letters; and if the walker crosses any number of bridges the number of letters denoting his route will be one greater than the number of bridges. Thus a crossing by seven bridges requires eight letters for its designation.
6. In this manner of denoting the crossings, I pay no attention to which bridges are used, but if the same crossing can be made from one region into another by several bridges, then it is just the same, whichever bridge be crossed, as long as the traveler reaches the designated region. From this it is clear that if the path over the seven bridges of the figure can be traced in such fashion that it crosses over each one once but over none twice, then this path can be represented by eight letters and these letters must be disposed in such fashion that the letters A and B occur directly next to each other twice, because there are two bridges a and b joining regions A and B; similarly, the two letters A and C also should occur twice in immediate succession in this series of eight letters; then the sequence of letters A and D should occur once, and similarly the sequence of letters B and D and C and D must occur once.
7. The question is reduced to this, then, that from the four letters A, B, C, and D a series of eight letters must be formed, in which all the sequences occur just as many times as we have indicated. However, before beginning work to find such an arrangement, it is convenient to show whether these letters can be disposed in this manner or not. For if it can be demonstrated that such an arrangement can by no means be made, all labor would be useless which was directed toward bringing this about. Wherefore I have searched for a rule, by means of which it could easily be ascertained-both for this question and for all similar ones-whether such an arrangement of letters can exist.
8. In order to find this rule I consider the single region A, into which any number of bridges a, b, c, d, etc. lead (Figure 7-2). Of all these bridges, I first pay attention to the single one a, which leads to the region A. If now the traveler crosses by way of this bridge, he necessarily must either have been in region A before he crosses, or must reach region A after the crossing. Therefore, according to the way of naming the crossing that I established above, it is necessary that the letter A occur once. If three bridges, say a, b, c, lead to region A and the traveler crosses over all three, then in naming his travel the letter A will occur twice, whether or not he started his course from A. Similarly, if five bridges lead to A, then in naming crossings by way of all five, the letter A must occur three times. And if the number of bridges be any odd number whatever, if we add one to this number and take half of it, this will give the number of times that letter A must occur.
9. To turn now to the case of the bridges that are to be crossed in Kiinigsberg. Because five bridges a, b, c, d, e lead to the island A, the letter A must occur three times in naming
the crossings over these bridges. Because three bridges lead to the region B, the letter B must occur twice, and similarly the letter D and the letter C must each occur twice. Hence in the series of eight letters, by which the crossing of seven bridges must be designated, the letter A should occur three times, and the letters B, C, and D each twice. But in a series of eight letters this can in no way be accomplished. From this it is clear that the required crossing over the seven bridges of Kiinigsberg cannot be done.
10. In similar fashion we can decide in any other case of bridges, if only the number which lead to any region is odd, whether each single bridge can be crossed just once. If it happens that the sum of all the times that each single letter should occur is equal to the number of all the bridges plus one, then such a crossing can be made. But if, as happened in our example, the sum of all the times should be greater than the number of bridges plus one, then such a crossing cannot be accomplished. The rule which I have given for finding the number of times of the letter A from the number of bridges leading into the region A, is equally valid whether all bridges come from one region B, as is the case in Figure 7-2, or whether they come from different regions; for I only consider the region A and inquire, how many times the letter A ought to occur.
11. If, however, the number of bridges leading to region A is even, then it must be known, in the matter of crossing each single bridge, whether the traveler began his course in A or not. For if two bridges lead to A and the traveler begins his course in A, then the letter A must occur twice; for it must once be present in order to denote the exit from A by one bridge, and once more in order to designate the reentry into A by way of the other bridge. But if the traveler begins his course in some other region, then the letter A will occur only once; for being written once it will denote both the arrival at A and the exit from A, in my manner of denoting such a course.
12. Now let four bridges lead into region A and let the traveler begin his course in A. In the designation of this course the letter A must be present three times, if he crosses over each single bridge once. But if he begins to walk in another region, then the letter A will occur only twice. If six bridges lead to the region A, then the letter A will occur four times, if the beginning of the walk is made at A; but if the traveler does not at the beginning come from A, then it will have to occur only three times. Generally therefore, if the number of bridges is even, one half of that number gives the number of times which the letter A must occur, if the beginning of the route is not in the region A; one half of the number of bridges plus one will give the number of times that the letter A must occur, if the beginning of the route is made in A itself.
13. But because in such a course the beginning can only be made in one region, I determine the number of times that the letter designating each region must occur from the number of bridges leading into the region, as half the sum of all the bridges plus one, if the number of bridges is odd; but as the half of the number of bridges themselves, if it is even. Then if the number of all the letter occurrences equals the number of the bridges. plus one, the desired course can successfully be traversed; but the beginning must be made from a region into which an odd number of bridges leads. If, however, the number of letter occurrences should happen to be less by one than that of the bridges plus one, then the course can successfully be traversed by beginning in a region into which an even number of bridges leads, because in this way the number of letter occurrences is increased by one.
14. Suppose then that any configuration whatever of water and bridges is given and that it is to be investigated whether it is possible to cross over each bridge once; I go about it in the following fashion: First, I name all regions that are separated by water from each other by the letters A, B, C, etc. Second, I take the number of all the bridges, add one to it, and place this number at the head of the succeeding calculation. Third, after the letters A, B, C, etc., written below one another, I write the number of bridges leading into the region. Fourth, I mark with an asterisk those letters that have even numbers after them. Fifth, I write half of the even number next to each of the even numbers, and I write a number equal to half of each odd number plus one next to each odd number. Sixth, I add together the numbers written in the last column. If this sum is equal to, or less by one than the number of bridges plus one-then I conclude that the desired crossing can be made. But it must be noted that, if the sum is one less than the number placed above, then the beginning of the route must be made in a region marked with an asterisk; on the other hand, from a region not so marked, if the sum is equal to the number in question. Thus in the case of Kiinigsberg I make the following calculations:
Number of bridges 7; key number, 8
A 5 3
B 3 2
C 3 2
D 3 2
Because this calculation results in a sum greater than 8, a crossing of this kind cannot be made in any way.
15. Let there be two islands A and B, surrounded by water, and let this water be connected with four rivers, as the figure (Figure 7-3) shows. So that the island can be reached let there be 15 bridges a, b, c, d, etc. across the water surrounding the islands and the rivers. The question is whether some course can
be found so that each of the bridges is crossed, but none more than once. First, therefore, I name all the regions which are separated by water from one another, by the letters A, B, C,D, E, F; there are six of these regions.Then I add one to the number 15 of the bridges, and place the sum 16 at the head of the following calculation:
Key number = 16
A* 8 4
B* 4 2
C* 4 2
D 3 2
E 5 3
F* 6 3 = 16
Third, I write the letters A, B, C, etc. under one another and with each I place the number of bridges that lead into this region, as 8 bridges lead to A, and four to B, etc. Fourth, those letters which have even numbers attached I mark with an asterisk. Fifth, in the third column I write half of the even numbers, but to the odd numbers I add one and write half of that. Sixth, I add the numbers of the third column to one another and obtain the sum 16. Since this is equal to the number 16 placed above the calculation, it follows that the crossing can be made in the desired fashion, if the course takes its beginnings either in region D or E, because these are not marked with an asterisk. The course could be made in this way:
where I placed the bridges by which the crossings are made between the capital letters.
16. By this reasoning it will be easy to judge in every case no matter how greatly complex, whether all bridges can be crossed just once, or not. I shall now relate a much easier way of discerning the same thing, which follows without great difficulty from the present way, after I have first made the following observations. First I observe that all the numbers of bridges, written in the second column after the letters A, B, C, etc. if added together are twice as great as the number of bridges. The reason of this is that in this calculation where all bridges leading into a given region are counted, each bridge is counted twice; for each bridge has reference to both regions which it joins.
17. From this observation it follows therefore that the sum of all the bridges which lead into each region is an even number, because its half is equal to the number of bridges. Hence it cannot happen that among the numbers of bridges leading into the several regions there is just one that is uneven; nor that three be uneven, nor five, etc. Hence if any of the numbers signifying the bridges, attached to the letters A, B, C, etc. are uneven, it is necessary that the number of these numbers be even. Thus in the example of Kiinigsberg there were four numbers of bridges that were odd, attached to the letters of the regions A, B, C, D, as can be seen from section 14. And in the preceding example, in section 15, there are only two odd numbers, attached to the letters D and E.
18. Since the sum of all thd numbers attached to the letters A, B, C, etc. equals twice the number of bridges, it is apparent that if two be added to this sum and the result divided by 2, then this must give the number placed at the head of the calculation. If, therefore, all the numbers attached to the letters A, B, C, D, etc. are even and in order to obtain the numbers of the third column half of each of them is taken, their sum will be less by one than the key number at the top. Therefore in such cases a crossing over the bridges can always be made. For in whatever region the course begins, it has bridges even in number leading to it, as is required. Thus in the Kiinigsberg case it would be possible for someone to cross over each bridge twice; each bridge could be, as it were, divided in two, and then the number of bridges leading into each region will be even.
19. Furthermore, if only two of the numbers attached to the letters A, B, C, etc. are odd, but all the others are even, then the desired crossing can always be successfully made, as long as the beginning of the course is in a region with which an odd number of bridges connect. For if the even numbers are halved as well as the odd numbers plus one, according to the rule, the sum of all these halves will be greater by one than the number of bridges and therefore equal to the key number at the head.
From this it will then 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 key number at the head and will exceed it by one or two or three etc. and hence the crossing cannot be made.
20. Hence if any case whatsoever be given, it can now very
easily be recognized whether a crossing over all bridges once
can be made or not, with the help of this rule:
If there are more than two regions which have an odd number of bridges leading to them, then it can with certainty be affirmed that such a crossing cannot be made.
If, however, there are two regions which have an odd number of bridges leading to them, then the crossing can be made, if the course begins in one of these regions.
If, finally, there are no regions which have odd numbers of bridges leading to them, then the desired crossing can be made, no matter in which region the beginning of the walk is made. This rule therefore fully solves the given problem.
21. But when it has been found that such a crossing can be made, the question still remains, how the course is to be found. For this I use the following rule: Let pairs of bridges which lead from one region to another, be eliminated in thought, as many times as it can be done. In this way, the number of bridges will be radically and quickly diminished. Then the desired course over the remaining bridges which can easily be done is looked for. When this has been found, it will at once be clear to anyone who attends to it that the bridges eliminated in thought will not disturb this course: and I judge it is not necessary for me to teach more about the finding of the course.