You are here

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

Author(s): 
Teo Paoletti

 

 

On August 26, 1735, Euler presents a paper containing the solution to the Konigsberg bridge problem.  He addresses both this specific problem, as well as a general solution with any number of landmasses and any number of bridges.  This paper, called ‘Solutio problematis ad geometriam situs pertinetis,’ was later published in 1741 [Hopkins, 2].  Euler’s paper is divided into twenty-one numbered paragraphs, and in what follows, a simplified version of Euler’s paragraphs will be presented.

In the first two paragraphs of Euler’s proof, he introduces the Konigsberg Bridge problem.  In Paragraph 1, Euler states that he believes this problem concerns geometry, but not the geometry well known by his contemporaries, that involves measurements and calculations, but instead a new kind of Geometry, which Leibniz referred to as Geometry of Position.  Then in Paragraph 2, Euler explains to his audience how the Konigsberg problem works.  Euler provided a sketch of the problem, which can be found to the right [not available], and called the seven distinct bridges: a, b, c, d, e, f, and, g.  In this paragraph he states the general question of the problem, “Can one find out whether or not it is possible to cross each bridge exactly once?” 

After stating the general question he is trying to solve, Euler begins to explore different methods of finding a solution.  In Paragraph 3, Euler tells the reader that to solve this specific problem, he could write down all possible paths, but this technique would take a great deal of time, and would not work for larger configurations with more bridges and land masses.  Because of these issues, Euler decided to choose a different method for solving this problem. 

In Paragraph 4, he begins simplifying the problem by inventing a convenient system to represent the crossing of a bridge.  Euler decides that instead of using the lowercase letters to represent the crossing of a bridge he would write the capital letters representing the landmasses.  For instance, referencing Figure 1 [not available], AB would signify a journey that started in landmass A, and ended in B.  Furthermore, if after traveling from landmass A to B, someone decides to move to landmass D, this would simply be denoted, ABD.  In Paragraph 5, Euler continues his discussion on this process explaining that in ABDC, although there are four capital letters, only three bridges were crossed.  Euler explains that no matter how many how many bridges there are, there will be one more letter to represent the necessary crossing.  Because of this, the whole of the Königsberg Bridge problem required seven bridges to be crossed, and therefore eight capital letters. 

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

Dummy View - NOT TO BE DELETED