You are here

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

Author(s): 
Teo Paoletti

In Paragraph 10, Euler continues his discussion by noting that if the situation involves all landmasses with an odd number of bridges, it is possible to tell whether a journey can be made using each bridge only once.  Euler states that if the sum of the number of times each letter must appear is one more then the total number of bridges, a journey can be made.  However, if the number of occurrences is greater than one more than the number of bridges, a journey cannot be made, like the Königsberg Bridge problem.  This is because the rule, which Euler gives for an odd number of bridges, using Figure 2 [not available], is true for the general situation whether there is only one other landmass or more than one. 

In Paragraphs 11 and 12, Euler deals with the situation where a region has an even number of bridges attached to it.  This situation does not appear in the Königsberg problem and, therefore, has been ignored until now.  In the situation with a landmass X with an even number of bridges, two cases can occur.  The first case is when X is the starting point for the journey.  In this case, X will appear twice, once as the starting point, and again as the ending point.  In the other case, X is not the starting point.  If this were to happen, X would only appear once, as the journey would have to enter through one bridge and immediately leave through the only other one available.  Similarly, if there are four bridges attached to X the number of occurrences of X depends on whether or not it is a starting point.  If the journey starts in X, it must appear three times, but if it does not begin in X, it would only appear twice.  So in general, if X has an even number of bridges attached, then if the journey does not start in X, X appears half the number of times as bridges (i.e. Occurrences of X where X is even and not the starting point = (# of Bridges) / 2).  If the journey does start in X then X appears half the number of times as bridges, plus one (i.e. Occurrences of X where X is even and starting point = ((# of Bridges) / 2) + 1). 

In Paragraphs 13 through 15, Euler explains how to figure out if a path using each bridge once and only once exists and presents his own example to show how it works.  Euler first explains his simple six-step method to solve any general situation with landmasses divided by rivers and connected by bridges.  First Euler denotes each landmass with a capital letter.  Second he takes the total number of bridges, adds one, and writes this above the chart he is about to make.  Next, he takes the capital letters, puts them in a column, and next to them writes the number of bridges.  Fourth, he indicates with asterisks the landmasses which have an even number of bridges.  Then, next to each even number, he writes ½ of the number and next to each odd number he places ½ the number plus one.  Finally, Euler adds the numbers written in the right-most column and if the sum is one less than, or equal to, the number of bridges plus one, then the required journey is possible.  It is important to note however, that if the sum is one less than the number of bridges plus one, then the journey must start from one of the landmasses marked with an asterisk.  If the sum is equal to the number of bridges plus one, the journey must start in a region not marked with an asterisk.

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

Dummy View - NOT TO BE DELETED