MENUEuler - A New Branch of Mathematics: Topology
PART II
Leonhard Euler lived from 1707-1783, during the period that is often called "the age of reason" or "the enlightenment." The French encyclopedists (men like Diderot and d'Alembert) worked to publish the first encyclopedia; Voltaire, living sometimes in France, sometimes in Germany, wrote novels, satires, and a philosophical dictionary; in Great Britain, George Berkeley and David Hume published important treatises on the theory of knowledge, while Edward Gibbon labored for twenty years on The Decline and Fall of the Roman Empire. Europe was in broad intellectual ferment, with all the arts and sciences flourishing.
An important part of Euler's scheme of solving problems consists in the proper labeling of the figure. He gives capital letters to each of the regions that are completely separated from each other by the river; there are four of them: A, B, C, D. (It is clear that in order for these four regions to be truly separated, we must conceive the river to go on indefinitely to the left; similarly, each of the two branches of the river on the right must continue indefinitely.) Then Euler designates the various bridges by small letters, a, b, c, d, e, f, g.
Next, he denotes the crossing from A to B by way of bridge a by the sequence of letters AaB, or, if no attention is paid to which bridge is used, the crossing from A to B is simply denoted by AB. Similarly going from B to D would be denoted by BfD, if we want to call attention to the bridge used, or simply by BD, if we do not. In the same fashion, going from A first to B and then to D is denoted by ABD. (Since no small letters are used, we do not know whether the crossing from A to B was by way of bridge a or b). Crossing over one bridge takes us from one region to a second one; and conversely, going from one region to a second one and from the second one to a third involves two bridges. In general, it is easy to see, the number of regions (that is, the number of capital letters) in a given course must be greater by one than the number of bridges crossed. In the Ktinigsberg problem, therefore, we know that if the required course can be traced, over seven bridges, it must be designated by eight letters.
Furthermore, since there are two bridges from A to B, the letters A and B must appear next to each other (either as AB or BA) twice in the sequence of eight letters; similarly, the letters A and C also must appear next to each other twice, while the letters AD (or DA ) , BD (or DB) , and CD (or DC) must each occur once. The question then is, Can a sequence of eight letters be formed in which this arrangement of letters holds? The whole rest of the paper is devoted to the problem of investigating the possibility of this letter sequence (or generally, other letter sequences of similar sort).
Euler reasons as follows. (The problem is made a little easier, as we shall see, because each of the four regions A, B, C, D, has an odd number of bridges leading to ic.) If a region has just one bridge leading to it, then the letter (say, A) of the region must occur just once, namely as either the starting point or the arrival point for a crossing. Suppose there are three bridges leading to the region A. Then the letter A must occur twice, whether the traveler starts in A or not. (See Figures 7-4a and 7-4b). And again, if there are five bridges lead-
ing to region A, then the letter A must occur three times. Generally, if there is an odd number of bridges leading to a region, the number of times which that letter must occur is equal to the number of bridges plus 1, divided by 2.
This immediately answers the question about the Kijnigsberg problem. Since five bridges lead to A, the letter A must occur three times. Since three bridges lead to B, the letter B must occur twice. Since three bridges lead to C, the letter C must occur twice. Finally, since three bridges lead to D, the letter D must occur twice. Thus the total sequence of letters must contain 3 A's, 2 B's, 2 C's, and 2 D's. But that is a total of 9 letters; yet the total sequence of letters is only supposed to consist of 8 letters (since each bridge is to be crossed just once.) Hence the problem is insoluble, since two incompatible conditions must be met: When we consider the problem as a whole, we find that just 8 letters must describe the series of crossings. When we consider the problem region by region, we find that a total of 9 letters is needed to describe the crossings. Thus Euler has proved what, he tells us, had always been suspected but had never been demonstrated-that the required course over the seven bridges cannot be traced. Euler immediately sets out to generalize his solution. He begins by investigating the situation when an even number of bridges leads to a region. Let us say that two bridges lead to region A. It immediately becomes apparent that it makes a difference whether the course begin at A or not. If two bridges lead to A, and the beginning of the course is in A, then the letter A will occur twice. 
But if two bridges lead to A, and the beginning of the course is not in A, then the letter A will occur only once.
Similarly, consider the case of four bridges leading to A. If the beginning of the course is at A, then the letter A must occur three times, but if the beginning of the course is not at A, then the letter A must occur just twice.
And the general rule is that if n is an even number of bridges leading to a region, then the number of times which the letter A must occur is equal to n/2 , if the beginning of the course is not in A. But if the beginning of the course is in A, then the number of times which the letter A must occur is given by n/2+ 1.
Suppose, then, that we have a problem where there are a number of regions, and where some of the regions have odd numbers of bridges leading to them, while others have even numbers of bridges leading to them. How can we determine how many times each letter must occur (when we consider the problem region by region) ? Euler's reasoning goes like this: Let us assume that the beginning of the course is in some region that has an odd number of bridges leading to it. Then the problem becomes perfectly determinate. For in the case of regions with odd numbers of bridges, it makes no difference where the course starts; consequently, I can determine the number of times that each letter designating an "odd" region must occur from the number of bridges. Now the rest of the problem is also determinate. For if the course starts in one of the "odd" regions, I can determine the number of times that each letter designating an "even" region must occur from the rule that applies when the start is not in an "even" region.
What if the beginning of the course is in one of the "even" regions? This means that for one region, but only one region, the number of times that the letter designating that region occurs must be increased by one. None of the other letter occurrences need to be changed, because as far as the other even regions go, the beginning of the course is still in a region other than themselves. And, of course, as far as the "odd" regions are concerned, the numbers of times that the letters designating them occur are not at all affected by where the beginning is made. So the rule for finding the number of times that the letters designating the various regions occur is very simple: For the "odd" regions take half of the sum obtained by adding one to the number of bridges; for the "even" regions take half of the number of bridges. This will give the number of letter occurrences, if the start of the course is in an "odd" region. If the start is in an "even" region, simply add one to the previous sum. If the sum is equal to the number of letter occurrences in the problem as a whole, it is soluble.
This solves the general problem, but Euler is still not satisfied. The general solution is too complicated for easy application, since we must consider each region separately and calculate the number of times that the letter of that region Wa occur from the number of bridges leading into it. Next, therefore, Euler derives a method that enables us to determine with hardly any calculation at all whether a crossing of the required kind can be made.
First, Euler notes that if we consider for each region how many bridges lead into it, and then add up these numbers, the resulting sum will be double the total number of bridges in the problem. For in the calculation region by region, each bridge is counted twice: The bridge connecting A and B is counted once as leading into A, and once as leading into B. This in turn means that the total number of bridges, when we count them region by region, must be an even number (for twice any number is an even number).
From this Euler concludes that there cannot be just one region that has an odd number of bridges leading into it (for then the sum of all bridges considered region by region would be odd) ; nor can there be three regions with odd numbers of bridges, for the same reason. In general, the number of "odd" regions cannot be odd but must be even.
What can we say about the number of times that each letter must occur? Suppose all the regions are "even"; then for each region the number of letter occurrences is equal to half of the bridges, except for one region. This one region-whichever it may be-is the one where the course starts; for this region the number of letter occurrences will be one greater than half of the bridges leading into it. If we, then, add up all the numbers of letter occurrences, we get this result: it would be equal exactly to the number of bridges; for the number of letter occurrences is equal to half the bridges, but the bridges are counted twice, when we go region by region. However, because we have to start in some one region, one more letter occurrence must be added. So, if all regions are "even," the letter occurrences are exactly equal to the number of bridges plus one. And that is how many times we saw the letters must occur when we consider the path as a whole. Euler concludes, therefore, that if all the regions are "even," the problem can always be solved.
If there are just two "odd" regions, the result will be the same, provided we start in an odd region. Each of the "even': regions now will give us letter occurrences equal to half the bridges. The two "odd" regions will each give us letter occurrences equal to one-half more than half the number of bridges. When we add up all the letter occurrences, therefore, we will find (since each bridge is considered twice), that we have a number equal to the number of bridges plus one. (But we must be sure to start the course in an "odd" region: otherwise, one more will be added from the fact that one of the "even" regions contains the start.)
If there are more than two "odd" regions, either four, or six, or more, the problem will not have a solution. Each two "odd" regions will add one to the number of letter occurrences above the number of bridges, and the result will be a number too large for the solution to be possible. (This is what happens in the Konigsberg problem.)
And so, as the result of Euler's analysis, we can say that "bridge" problems similar to the Kiinigsberg problem can be solved, provided all the regions are "even" or no more than two regions are "odd." If we have two ‘odd" regions, then we must start the course in one of the odd regions.
Now let us make a slight switch on Euler's problem. Let us replace the picture of river, island, and bridges with a different diagram. Let each of the four regions A, B, C, D be replaced by a point. Let each of the seven bridges a, b, c, d, e, f, g be replaced by a line joining two of the points. The Konigsberg diagram will then become like the figure.
Why is it legitimate to replace entire "regions" by points? For the purposes of Euler's problem, there is no real difference between his regions and points. The basic and essential fact about the four regions is that they must be totally unconnected except by bridges. And this is exactly the case with four points located in space. They have no connection until we draw lines joining them (corresponding to the bridges). It is also apparent that there are any number of equivalent diagrams that I could draw for the Kiinigsberg problem. For example, consider figures. Each one of them is the "same" as the Konigsberg diagram.
Euler's general problem may now be stated as follows: Given any figure consisting only of lines joining a number of vertices, can we determine whether such a figure can be traced
by a continuous line, without any part of the line being retraced? and the answer which Euler has found is this: Consider each vertex. Count the lines joining this vertex. If all the vertices are joined to others by even numbers of lines, the problem has a solution. If two of the vertices are joined to others by odd numbers of lines, the problem still has a solution, but we must start to trace our line from one of the "odd" vertices. If more than two vertices are joined by odd numbers of lines, the problem is not soluble.
Look at the three diagrams. Although they become progressively more complicated, the simplest one
cannot be traced in one continuous line, because it has four "odd" vertices (that is, four vertices where three limes come together). The second draw can be drawn in one continuous line, provided we start at one of the two vertices marked "3," while the third one can be drawn no matter where we start.
Now we can look back and indicate in a general sort of way what topology is. It is obviously a branch of geometry, in that it deals with points and lines. However, it does not treat these elements in any metric way; that is, it is not interested in size relationships. It is interested only in relative position. That is why Leibniz, as Euler tells us at the beginning of his little piece, called this branch of geometry "geometry of position." It is also sometimes called "analysis situs," which is merely a Latin way of saying that it analyzes position. (These names have an advantage over topology in that the latter name is nowadays used in a wider sense.) In general, geometry of position deals with properties that remain constant (invariant) when size and distance relationships are distorted.
If you look again at the three diagrams in the previous figure , you can see how uninterested topology is in absolute size, of lines, angles, etc., and even in whether a iine is straight or curved. From the topological point of view, all three figures are exactly the same. Similarly, a triangle, a square, and a circle are exactly the same from the point of view of topology, because each of these figures divides the plane into two parts, one "inside" the figure, the other one "outside" it. Furthermore, it is of no importance how big the closed figure is; topologically the situation is exactly the same.
Euler's problem, it is apparent, has nothing to do with measurement. The only question is this: Can a continuous line be drawn, through the four points, A, B, C, D, connecting A and B twice, A and C twice, A and D once, B and C not at all, B and D once, C and D once, with the continuous line crossing itself only at the four points A, B, C, D? The answer, we have just learned, is No.
Another typical topological problem is that of determining the inside and outside for a given figure. This may seem like no problem at all. In a triangle, for example, it is obvious what is inside the figure and what is outside. But there are other figures for which this determination is a problem. Consider the famous Moebius strip (named after its discoverer). We obtain this strip by taking a long, thin rectangle and bending it so as to connect one end with the other. However, before making the final connection (by pasting or in some other way) we twist the rectangle so as to place C on A and D on B.
The resulting figure is the Moebius strip.
If we trace a line parallel to the two long sides of the rettangle (such as the dotted line in the figure), we find that although we start on the "outside" of the strip, pretty soon we are on the "inside" of it. If you puncture the strip somewhere along the dotted line and then make a cut following that line, all the way around, you will find that the strip has not been separated in two parts. It is still one whole!
The coloring of maps gives rise to a fascinating puzzle that belongs to topology: We wish to color a map in such a fashion that the same color shall not appear on both sides of a boundary between two countries. (If several countries come together at only one point, then the same color may be used.) The problem is: If the map is drawn on a plane surface, what is the least number of colors that have to be used? This is one of those problems, like the one of the Kiinigsberg bridges, where everyone is pretty sure of the answer, but no one has been able to prove that the answer is correct. You will lose no money if you bet that four colors are suflkient, but mathematically speaking, the problem is still unsolved. Incidentally, it has been proved that at most five colors need to be used for a map on a plane surface.
