You are here

Leonard Euler's Solution to the Konigsberg Bridge Problem - Euler's Conclusions

Author(s): 
Teo Paoletti

In the next few paragraphs, Euler presents another way to figure out if a journey can be made given any set of landmasses, bridges, and rivers.  In Paragraph 16, Euler points out that the total of the numbers listed directly to the right of the landmasses adds up to twice the total number of bridges.  This fact later becomes known as the handshaking lemma.  Basically, the handshaking lemma states that each bridge is counted twice, once for each landmass to which it is attached.  In Paragraph 17, Euler goes on to state that the sum of all the bridges leading to each region is even, since half of this number is equal to the total number of bridges.  However, this is impossible if there are an odd number of landmasses with an odd number of bridges.  Therefore, Euler proves that if there are some odd numbers attached to land masses, there must be an even number of these landmasses. 

However, this is not enough to prove when there is a path where each bridge is used once and only once, as the Königsberg Bridge problem has an even number of landmasses with an odd number of bridges going to them.  Because of this, Euler adds more restrictions in Paragraphs 18 and 19.  Euler explains that since the total of the numbers of bridges attached to each landmass is equal to twice the number of bridges (as seen in the handshaking lemma), so therefore if you add two to this sum and then divide by two, you will get the number of total bridges plus one.  This number is the same as the one used before, which is used to tell if a path is possible.  If all the numbers are even, then the third column in the table will sum to one less than the total number of bridges plus one. 

Euler then explains that it is obvious that if there are two landmasses with an odd number of bridges then the journey will always be possible if the journey starts in one of the regions with an odd number of bridges.  This is because if the even numbers are halved, and each of the odd ones are increased by one and halved, the sum of these halves will equal one more then the total number of bridges.  However, if there are four or more landmasses with an odd number of bridges, then it is impossible for there to be a path.  This is because the sum of the halves of the odd numbers plus one along with the sum of all of the halves of the even numbers will make the sum of the third column greater than the total number of bridges plus one.  Therefore, Euler just proved that there can be at most two landmasses with an odd number of bridges. 

With this being stated, Euler can now make his conclusions concerning more general forms of the Königsberg Bridge problem.  In Paragraph 20, Euler gives the three guidelines that someone can use to figure out if a path exists using each bridge once and only once.  First, he claimed if there are more than two landmasses with an odd number of bridges, then no such journey is possible.  Second, if the number of bridges is odd for exactly two landmasses, then the journey is possible if it starts in one of the two odd numbered landmasses.  Finally, Euler states that if there are no regions with an odd number of landmasses then the journey can be accomplished starting in any region.  After stating these three facts, Euler concludes his proof with Paragraph 21, which simply states that after one figures out that a path exists, they still must go through the effort to write out a path that works.  Euler believed the method to accomplish this was trivial, and he did not want to spend a great deal of time on it.  However, Euler did suggest concentrating on how to get from one landmass to the other, instead of concentrating on the specific bridges at first. 

 

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