You are here

Leonard Euler's Solution to the Konigsberg Bridge Problem - Euler's Proof, Part II

Teo Paoletti

In Paragraph 6, Euler continues explaining the details of his method.  He tells the reader that if there is more than one bridge that can be crossed when going from one landmass to the other, it does not matter which bridge is used.  For example, even though there are two bridges, a and b, that can take a traveler from A to B, it does not matter with Euler’s notation which bridge is taken.  In this paragraph, Euler also discusses the specific problem he is dealing with.  He explains, using his original figure, that the Königsberg problem needs exactly eight letters, where the pairs of (A,B) and (A,C) must appear next to each other exactly twice, no matter which letter appears first.  In addition, the pairs (A,D), (B,C), and (C,D) must occur together exactly once for a path that crosses each bridge once and only once to exist. 

In Paragraph 7, Euler informs the reader that either he needs to find an eight-letter sequence that satisfies the problem, or he needs to prove that no such sequence exists.  Before he does this for the Königsberg Bridge problem, he decides to find a rule to discover whether a path exists for a more general problem.  He does this in Paragraph 8 by looking at much simpler example of landmasses and bridges.  Euler draws Figure 2 [not available], and he begins to assess the situations where region A is traveled through.  Euler states that if bridge a is traveled once, A was either where the journey began or ended, and therefore was only used once.  If bridges a, b, and c are all traveled once, A is used exactly twice, no matter if it is the starting or ending place.  Similarly, if five bridges lead to A, the landmass A would occur exactly three times in the journey.  Euler states that, “In general, if the number of bridges is any odd number, and if it is increased by one, then the number of occurrences of A is half of the result.”  In other words, if there is an odd number of bridges connecting A to other landmasses, add one to the number of bridges, and divide it by two, to find out how many total times A must be used in the path, where each bridge is used once and only once (i.e. Total Occurrences of A where A has an odd # of bridges = (# of Bridges - 1) / 2 ). 

Using this fact Euler solves the Königsberg bridge problem in Paragraph 9.  In that case, since there are five bridges that lead to A, it must occur three times. (See Figure 1 [not available], reproduced here for easy access.)  Similarly, B, C, and D must appear twice since they all have three bridges that lead to them.  Therefore 3(for A) + 2(for B) + 2(for C) + 2(for D) = 9, but Euler already stated that there must only be eight occurrences for the seven bridges.  This is a contradiction!  Therefore, it is impossible to travel the bridges in the city on Königsberg once and only once.  The end, or is it?  While the people of Königsberg may be happy with this solution, the great mathematician Leonhard Euler was not satisfied.  Euler further continues his proof to deal with more general situations. 

Teo Paoletti, "Leonard Euler's Solution to the Konigsberg Bridge Problem - Euler's Proof, Part II," Convergence (May 2011)