You are here

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

Author(s): 
Teo Paoletti

Using the Konigsberg problem has his first example Euler shows the following:

                   Number of bridges = 7, Number of bridges plus one = 8

                     Region    Bridges            Times Region Must Appear

                        A             5                                     3

                        B             3                                     2

                        C             3                                     2

                        D             3                                     2

However, 3 + 2 + 2 + 2 = 9, which is more than 8, so the journey is impossible.

Since this example is rather basic, Euler decides to design his own situation with two islands, four rivers, and fifteen bridges.  The situation Euler created can be seen in Figure 3 [not available].  Euler now attempts to figure out whether there is a path that allows someone to go over each bridge once and only once.  Euler follows the same steps as above, naming the five different regions with capital letters, and creates a table to check it if is possible, like the following:

                        Number of bridges = 15, Number of bridges plus one = 16

                                    Region  Bridges      Times Region Must Appear

                                    A*            8                           4

                                    B*            4                           2

                                    C*            4                           2

                                    D              3                           2

                                    E              5                           3

                                    F*            6                           3

In addition, 4 + 2 + 2 + 2 + 3 + 3 = 16, which equals the number of bridges, plus one, which means the journey is, in fact, possible.  Since the sum equals the number of bridges plus one, the journey must start in either D or E.  Now that Euler knows it is possible to make a journey, all he needs to do is state what the path will be.  Euler chooses the path EaFbBcFdAeFfCgAhCiDkAmEnApBoElD, where he includes which bridges are crossed between the letters representing the landmasses.  While this information is extraneous, as the exact bridge does not matter in knowing that a journey is possible, it is useful when selecting a path.  This is a good example that shows the method which Euler would use when solving any problem of this nature. 

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

Dummy View - NOT TO BE DELETED