Background
The great Swiss mathematician Leonhard Euler, who had been asked by the Mayor of Danzig to provide a solution to the Königsberg Bridge problem, sent him this disdainful reply:
“. . . Thus you see, most noble Sir, how this type of solution bears little relationship to mathematics, and I do not understand why you expect a mathematician to produce it, rather than anyone else, for the solution is based on reason alone, and its discovery does not depend on any mathematical principle. Because of this, I do not know why even questions which bear so little relationship to mathematics are solved more quickly by mathematicians than by others.”
However in the same year he wrote this, in a letter to the Italian mathematician and engineer, Giovanni Marinoni.
“This question is so banal, but seemed to me worthy of attention in that [neither] geometry, nor algebra, nor even the art of counting was sufficient to solve it.”
On August 26, 1735, Euler presented a paper containing the solution to the Königsberg bridge problem, in which he addresses both the specific problem, and gives a general solution with any number of land masses and any number of bridges. This paper, titled ‘Solutio problematis ad geometriam situs pertinentis,’ was published later in 1741. What follows is a verbatim version of an edited version of this paper translated by James R.Newman, that appeared in my 1978 set of reprints from Scientific American entitled, ‘Mathematics: An Introduction to its Spirit and Use’. I have just reinstated the paragraph numbering from the original paper.
Euler’s Paper
1. The branch of geometry that deals with magnitudes has been zealously studied throughout the past, but there is another branch that was then almost unknown up to now; Leibnitz spoke of this first, calling it the “geometry of position” (geometry situs). This branch of geometry deals with relations dependent on position alone, and investigates the properties of position; it does not take magnitude into consideration, nor does it involve calculation with quantities. But as yet no satisfactory definition has been given of the problems that belong to this geometry of position or of the method to be used in solving them. Recently there was announced a problem which, whilst it certainly seemed to belong to geometry, was nevertheless so designed that it did not call for the determination of a magnitude, nor could it be solved by quantitative calculation, consequently I did not hesitate to assign it to the geometry of position, especially since the solution required only the consideration of position, calculation being of no use. In this paper I shall give an account of the method that I discovered for solving this type of problem, which may serve as an example of the geometry of position.
2. The problem, which I understand is quite well known, is stated as follows: In the town of Königsberg in Prussia there is an island A called Kneiphof, with two branches of the river Pregel flowing round it. There are seven bridges a, b, c, d, e, f and g crossing the two branches of the river. The question is whether a person can plan a walk in such a way that he will cross each of these bridges once but not more than once. I was told that while some denied the possibility of doing this and others were in doubt, no one maintained that it was actually possible. On the basis of the above I formulated the following very general problem for myself: Given any configuration of the river and branches into which it may divide, as well as any number of bridges, to determine whether or not it is possible to cross each bridge exactly once.
3. The particular problem of the seven bridges of Königsberg could be solved by carefully tabulating all possible paths, thereby ascertaining by inspection which of them, if any, met the requirement. This method of solution, however, is too tedious and too difficult because of the large number of possible combinations, and in other problems where many bridges are involved it could not be used at all. Hence I discarded it and searched for another more restricted in its scope; namely, a method which would show only whether a journey satisfying the prescribed condition could in the first instance be discovered; such an approach, I believed, would be simpler.
4. My entire method rests on the the appropriate and convenient way in which I denote the crossing of bridges, in that I use capital letters A, B, C, D, to designate the various areas of land that are separated from one another by the river. Thus when a person passes from area A to area B, using either of the two possible bridges a or b, I denote this by the letters AB, the first of which denotes the area whence he came and the second the area where he arrives after crossing the bridge. If the traveller then crosses from B over bridge f into D, this crossing is denoted by the letters BD; the two crossings AB and BD performed in succession I denotes simply by the three letters ABD, since the middle letter B designates the area into which the first crossing leads as well as the area out of which the second leads.
5. Similarly, if the traveller proceeds from D across bridge g into C, I designate the three successive crossings by the four letters ABDC. The crossing of four bridges will be represented by five letters and if the traveller crosses an arbitrary number of bridges his journey will be described by a number of letters that is one greater than the number of bridges. For example, eight letters are needed to denote the crossing of seven bridges.
6. With this method I pay no attention to which bridges are used; if the crossing from one area to another can be made by one of several bridges it makes no difference which is used, so long as it leads to the desired area. Thus if a route could be laid out over the seven Königsberg bridges so that each bridge was only crossed once and only once, it would be possible to describe this route using eight letters, and in this series of letters AB (or BA) would have to occur twice since there are two bridges (a and b) connecting the areas A and B. Similarly the combination AC would occur twice and the combinations AD, BD and CD would each occur once.
7. Our question is now reduced to whether from the four letters A, B, C and D a series of eight letters can be formed in which all the combinations just mentioned occur the required number of times. Before making the effort, however, I think it well to consider whether its existence is even theoretically possible or not. For if it could be shown that such an arrangement is in fact impossible, then the effort expended on trying to find it would be wasted. Therefore I have sought for a rule that would determine without difficulty, as regards this and similar questions, whether the required arrangement of letters is feasible.
8. For the purposes of finding such a rule I take a single region A into which an arbitrary number of bridges a, b, c, d, etc. lead. Of these bridges I first consider only a. If the traveller crosses this bridge, he must either first have been in A before crossing or have reached A after crossing, so that according to the above method of denotation the letter A will appear exactly once. If there are three bridges leading to A and the traveller crosses all three, the letter A will occur twice in the expression representing his journey, whether it begins at A or not. And if there are five bridges leading to A, the expression for a route that crosses them all will contain the letter A three times. If the number of bridges is odd, increase it by one, and take half the sum; the quotient (the answer) represents the number of times the letter A appears.
9. Let us now return to the Königsberg problem. Since there are five bridges leading to (and from) island A, the letter A must occur three times in the expression describing the route. The letter B must occur twice, since three bridges lead to B; similarly D and C must both occur twice. That is to say, the series of letters that represents the crossing of the seven bridges must contain A three times and B, C, and D each twice. But this is quite impossible with a series of eight letters, for the sum of the required letters is nine ( 3 + 2 + 2 + 2 = 9). Thus it is apparent that a crossing of the seven bridges in the manner required cannot be effected.
10. Using this method we are always able, whenever the number of bridges leading to a particular region is odd, to determine whether it is possible in a journey to cross each bridge exactly once. Such a route exists if the number of bridges plus one is equal to the sum of the numbers which indicate how often each individual letter must occur. On the other hand if this sum is greater than the number of bridges plus one, as it is in our example, then the desired route cannot be constructed. The rule that I give for determining from the number of bridges that lead to A how often the letter A will occur in the route description is independent of whether these bridges all come from a single region B or from several regions, because I was considering only the region A, and attempting to determine how often the letter A must occur.
11. When the number of bridges leading to A is even, we must take into account whether the route begins in A or not. For example, if there are two bridges that lead to A and the route starts from A, then the letter A will occur twice; once to indicate departure from A by one of the bridges and a second time to indicate the return to A by the other bridge. However, if the traveller starts his journey in another region, the letter A will only occur once, since by my method of description the single occurrence of A indicates an entrance into as well as a departure from A.
12. Suppose, as in our case, there are four bridges leading into the region A, and the route is to begin at A. The letter A will then occur three times in the expression for the whole route, while if the journey had started in another region, A would only occur twice. With six bridges leading to A, the letter A will occur four times if A is the starting point, otherwise only three times. In general, if the number of bridges is even, the number of occurrences of the letter A, when the starting region is not A, will be half the number of bridges; when the route starts from A, one more than half.
13. Every route must, of course, start in some one region. Thus from the number of bridges that lead to each region I determine the number of times that the corresponding letter will occur in the expression describing the whole route as follows: When the number of bridges is odd, I increase it by one and divide by two; when the number is even I simply divide it by two. Then if the sum of the resulting numbers is equal to the number of bridges plus one, the journey can be accomplished, though it must start in a region approached by an odd number of bridges. But if the sum is one less than the number of bridges plus one, the journey is feasible if its starting point is approached from a region with an even number of bridges, for in that case the sum is again increased by one.
14. My procedure for determining whether in any system of rivers and bridges it is possible to cross each bridge exactly once is as follows: First I designate the individual regions separated from one another by water A, B, C, etc. Second, I take the total number of bridges, increases it by one, and write the resulting number at the top of the page. Third, under this number I write the letters A, B, C, etc. in a column, and opposite each letter note the number of bridges that lead to that particular region. Fourth, I place an asterisk again each letter that has an even number next to it. Fifth, in a third column I write opposite each even number half of that number and opposite each odd number half the sum formed by that number plus one. Sixth, I add up the last column of numbers. If the sum is one less or equal to the number at the top, I conclude that the required journey can be made. But it must be noted that when the sum is one less than the number at the top, the route must start from a region marked with an asterisk, and when the two numbers are equal, it must start from a region that does not have an asterisk.
For the Königsberg problem, I would set up the tabulation as follows:
The last column now adds up to more than 8, and hence the required journey cannot be made.
15. Let us take an example of two islands with four rivers forming the surrounding water.
Fifteen bridges marked a, b, c, d, etc. cross the water round the two islands and the adjoining rivers. The question is whether a journey can be arranged that will pass over all the bridges , but not over any more than once. I begin by marking the regions that are separated from one another by water with the letters A, B, C, D, E and F, there are six of them. Second, I take the number of bridges (15) add one and write the number (16) uppermost. Third, I write the letters A, B, C, etc in a column and opposite each letter write the number of bridges connecting with that region, e.g. eight bridges for A, four for B, etc. Fourth, the letters that have even numbers against them are marked with an asterisk. Fifth, in a third column I write the half of each corresponding number, or if the number is odd, I add one to it, and put down half the sum. Sixth, I add the numbers in the third column and gets 16 as the sum.
The sum of the third column is the same as the number 16 that appears above, and it follows that the journey can be effected if it begins in regions D or E, whose symbols have no asterisks. The following expression represents such a route:
EaFbBcFdAeFfCgAhCiDkAmEnApBoElD
Here I have indicated, by small letters between the capitals, which bridges are crossed.
16. By this method we can easily determine, even in cases of considerable complexity, whether a single crossing of each bridge in sequence is possible. But I should now like to give another and much simpler method which follows quite easily from the preceding, after a few preliminary remarks. In the first place I note that the sum of the numbers written down in the second column is necessarily double the actual number of bridges. The reason is that in the tabulation of the bridges leading to the various regions each bridge is counted twice, once for each of the two regions that it connects.
17. From this observation it follows that the sum of the numbers in the second column must be an even number, since half of it represents the actual number of bridges. Hence, if any of the numbers opposite the letters A, B, C, etc. are odd an even number of them must be odd. In the Königsberg problem for instance, all four of the numbers opposite the letters A, B, C, D, were odd, while in the example just given only two of the numbers were odd, namely those opposite D and E.
18. Since the sum of the numbers opposite A, B, C, etc. is double the number of bridges, it is clear that if this sum is increased by two in the latter example and then divided by two, the result will be the number written at the top. When all the numbers in the second column are even, and half of each is written down in the third column, the total of this column will be one less than the number at the top. In that case it will always be possible to cross all the bridges. For in whatever region the journey begins, there will be an even number of bridges leading to it, which is the requirement.
19. Further, when only two of the numbers opposite the letters are odd, and the others even, the required route is possible provided it begins in a region approached by an odd number of bridges. We take half of each even number, and likewise half of each odd number after adding one, as our procedure requires: the sum of these halves will then be one greater than the number of bridges, and hence equal to the number written at the top. But, when more than two of the numbers in the second column are odd, it is evident that the sum of the numbers in the third column will be greater than the top number and hence the desired journey is impossible.
20. Thus for any configuration that may arise the easiest way of determining whether a single crossing of all the bridges is possible is to apply the following rules:
If there are more than two regions which are approached by an odd number of bridges, no route satisfying the required conditions can be found.
If, however, there are only two regions with an odd number of approach bridges the required journey can be completed provided it originates in one of these regions.
If, finally, there is no region with an odd number of approach bridges, the required journey can be effected, no matter where it begins.
These rules solve completely the problem initially proposed.
21. After having determined that a route actually exists we are left with the question of how to find it. To this end the following rule will serve: Wherever possible we mentally eliminate any two bridges that connect the same two regions; this usually reduces the number of bridges considerably. Then, and this should not be too difficult, we proceed to trace the required route across the remaining bridges. The pattern of this route, once found, will not be substantially affected by the restoration of the bridges which were first eliminated from consideration, as a little thought will show. Therefore I do not think I need say no more about finding the routes themselves.
Commentary
After overcoming his initial reluctance to solve such a banal problem, in Section 1, Euler relates the problem to an emerging area of mathematical enquiry, the geometry of position. In Section 2, he states the problem clearly and labels the island Kneiphof A and the bridges a, b, c, d, e, f and g. In Section 3, although Euler recognises that the problem could be solved by enumerating all routes, he rejects this method as being too tedious, too difficult and not capable of being extended.
In Sections 4, 5 and 6, Euler establishes his method of notation, labelling the separate land areas A, B, C, and D, and paths or journeys, from one area to another, as strings of these letters ABDC etc. paying no attention to which bridge might be used to get from one area to another. He then notes that with his notation, to represent the crossing of the seven bridges needs a string of eight letters, and that the combination AB or (BA) would need to appear twice as would the combination AC (each with two bridges), whilst the combinations AD, BD and CD would each appear once (each with only one bridge).
In Section 7, Euler notes that the problem is now reduced to whether from the four letters, A, B, C, and D a series of eight letters can be formed in which all the combinations just mentioned can occur. But before wasting effort on looking for possible arrangement he wishes to see if he can find a simple rule that says whether any arrangement is possible. In Section 8, he imagines a single area A into which an arbitrary number of bridges a, b, c, d, etc. lead. He first considers only bridge a, and notes that if the traveller crosses this bridge he must either have come from A or arrived in A and therefore the letter A will appear exactly once. If there are three bridges leading to A the letter A will appear twice and if there are five bridges it will appear three times.
So the problem as stated requires that there are only eight letters in the string representing the required route, but also requires that A appears three times and B, C, and D each appear twice, a total of nine times ( 3 + (3 x 2) = 9). The requirements are contradictory and therefore no route is possible.
Having solved the presented problem, Euler then proceeds to generalise his method and provides a step by step algorithm for solving problems with any number of islands and any number of bridges. But Euler is still not satisfied and proceeds to produce a yet simpler set of three rules that determine in any situation, if all bridges can be crossed once without any being crossed twice.
Planar Graphs
Whilst Euler’s paper is widely recognised as the origin of Graph Theory, it is interesting to note that it does not actually contain anything that looks like a graph, its major contribution being the notation adopted. By long custom, in Euclidean Geometry capital letters, A, B, C etc. denote points, and lowercase letters, a, b, c etc. edges. Euler uses capital letters to represent areas and lowercase letters to represent bridges (the connections between areas). This facilitates the idea that areas can be represented by points and connections by edges. So that the Königsberg Bridges problem can be represented graphically as follows:-
With graphs like this, one can easily count the number of nodes that have an odd number of edges entering them, marked red above. If there are more than 2 nodes with an odd number of edges then no route is possible, but if there are just 2 nodes with an odd number of edges then it is possible to find a route, provided that you start from one of the odd nodes.
As noted by Euler, where there are two (or any even number of) bridges between two regions these can be ignored because the traveller can use one bridge to go from say A to C and the other one to come back from C to A, completing a cycle, eliminating both bridges and leaving him where he started from, and able to proceed to another bridge.
In recognition of Euler’s contribution to Graph Theory, routes that visit each node once but none more than once are called Euler Cycles. Euler’s solution also applies to another banal problem, that I learnt at school, drawing figures without removing your pencil from the page.
A coloured map can be represented as a planar graph if the coloured regions of the map are replaced by same coloured vertices in the graph, and vertices are joined by an edge in the graph if their corresponding regions in the map share an edge.
In fact the planar graph is a dual of the map, and the map can be generated from the graph. Both map and graph obey, another contribution of Euler to Graph Theory, his formula for networks; regions + vertices – edges = 1. In the examples above 7 regions + 11 vertices – 17 edges = 1 for the map and 10 regions + 8 vertices – 17 edges = 1 for the graph.
The planar graph is therefore an exact equivalent of the map and the Four Colour Conjecture can be expressed as seeing if the vertices of the graph can be coloured with 4 colours so that no 2 adjacent vertices have the same colour.
More importantly planar graphs lend themselves to computer manipulation, and this in turn has lead to a, somewhat disputed, computer enabled proof of the four colour theorem. See here for more detail.
Directed Graphs
With planar graphs an edge (or arc) between two nodes A and B, is bi-directional and acts like a bridge that allows movement from B to A as well as from A to B, and can therefore only represent a symmetrical relation between A and B, like adjacency. On the other hand, in directed graphs, edges are defined as having a direction, so that an edge from A to B acts like a turnstile or valve allowing movement from A to B but preventing movement from B to A. This allows values to be added to each edge, so that flows, electrical currents, dimensions etc. can be represented and networks modelled.
See here for details of Kirchhoff’s Laws for electrical flow in wires being applied to the automatic generation of house plans. Directed graphs also form the basis of Precedence Graphs, Critical Path Analysis and modern Graphical Programming Systems like Grasshopper where inputs are on the left hand edge of each block, outputs on the right and scripted procedures can be added to the block itself.
Bibliography
Appel, K., Haken, W. and Koch, J. (1977) Every Planar Map is Four Colorable. I: Discharging. Illinois J. Math. 21, 429-490
Appel, K. and Haken, W. (1977 ) Every Planar Map is Four-Colorable, II: Reducibility. Illinois J. Math. 21, 491-567.
Euler, L. (1736) Solutio problematis ad geometriam situs pertinentis. Comment. Acad. Sci. U. Petrop. 8, 128-140. Reprinted in Opera Omnia Series Prima, Vol. 7. pp. 1-10, 1766.
Hopkins B. and Wilson R. (2004) The Truth about Königsberg. College Mathematics Journal , 35, 198-207
March, L. and Steadman, P. (1971) The Geometry of Environment. RIBA Publications Ltd.
Newman J. R. (1953) The Königsberg Bridges. In Mathematics: An Introduction to its Spirit and Use, Scientific American. June 1978 22 121-124.
Steadman, P. (1970) The Automatic Generation of Minimum Standard House Plans Working Paper 23 University of Cambridge Land Use and Built Form Studies
Tutte, W. T. (1958) Squaring the Square from ‘Mathematical Games’ column, Scientific American Nov 1958.
grahamshawcross.com 