	KONIGSBERG'S BRIDGES		Contact Us At Contra Costa College	Math Dept. Home Page

Euler's Konigsberg's Bridges Problem

hands The river Pregel divides the town of Konigsberg into four separate land masses, A, B, C, and D. Seven bridges connect the various parts of town, and some of the town's curious citizens wondered if it were possible to take a journey across all seven bridges without having to cross any bridge more than once. All who tried ended up in failure, including the Swiss mathematician, Leonhard Euler (1707-1783)(pronounced "oiler"), a notable genius of the eighteenth-century.
However, Euler did succeed in explaining why such a journey was impossible, not only for the Konigsberg bridges, but whether such a journey was possible or not for any network of bridges anywhere. Euler reasoned that for such a journey to be possible that each land mass should have an even number of bridges connected to it, or if the journey would begin at one land mass and end at another, then exactly those two land masses could have an odd number of connecting bridges while all other land masses must have an even number of connecting bridges.

A matter of odds and evens...

Euler recognized that in order to succeed, a traveler in the middle of the journey must enter a land mass via one bridge and leave by another, thus that land mass must have an even number of connecting bridges. Further, if the traveler at the start of the journey leaves one land mass, then a single bridge will suffice and upon completing the journey the traveler may again only require a single bridge to reach the ending point of the journey. The starting and ending points then, are allowed to have an odd number of bridges. But if the starting and ending point are to be the same land mass, then it and all other land masses must have an even number of connecting bridges.
Alas, all the land masses of Konigsberg have an odd number of connecting bridges and the journey that would take a traveler across all the bridges, one and only one time during the journey, proves to be impossible!

Bridge Graph Diagram of the Bridges

If we draw a diagram of the situation where the land masses are represented by points and the bridges are represented by arcs or line segments, we might get a figure like the one at the left.
Now our problem is to start at a vertex and to traverse the diagram, say with a pencil, without lifting the pencil so that we travel over each arc or line segment, but not more than once.
In this figure we can designate the points (vertices) as 'odd' or 'even' by the number of arcs or line segments emanating from each vertex. Thus, vertex A is 'odd' since there are 5 arcs emanating from it. By inspection each of the other vertices is also 'odd'.
Because there are more than two odd vertices, it is not possible to trace the figure without traveling along the same arc or line segment more than once (while not lifting our pencil off the figure).

Problem:     See if you can traverse each of the next figures without lifting your finger
    off the surface and without travelling along the same line segment twice.
    Click on Answer to check the ones that can be so traced.

Newbridge Intersecting Figures Newgraph Newgraph2 Classical

A

B

C

D

E

So, what about the pentagram below?

?

Problem:         In the Great Hall of Mathematical Learning there are 12 rooms with various
    connecting doorways (See floor plan below). The main entrances are on the north side
    of the building. (There are some exits on the south side that are not shown, because these
    are locked for this problem and are not to be considered.)
    Using your Eulerian Knowledge, determine whether a person can take a walk through
    and around this building and pass through each and every doorway shown, without
    passing through any doorway more than once.

Great Hall

"Liesez Euler, Liesez Euler, c'est notre maître à tous"
("Read Euler, read Euler, he is our master in everything") - Laplace

For more about Euler and his other works, see C. Boyer & U. Merzbach, A History of Mathematics, 2nd. Ed., Wiley Pub., Chap. 21, "The Age of Euler".

Or William Dunham, EULER: THE MASTER OF US ALL, Mathematical Association of America, 1999.

Online follow the links below:

   Mathematicians of the Seventeenth and Eighteenth Centuries, from
   A Short Account of the History of Mathematics by W. W. Rouse Ball
      Page maintained by:
      David R. Wilkins - Trinity College, Dublin          http://www.maths.tcd.ie/pub/HistMath/

   Real Analysis - Historical Tidbits
      Page maintained by:     Bert G. Wachsmuth & Paul Golba - Seton Hall University
         http://www.shu.edu/html/teaching/math/reals/history/

   from Eric Weisstein's World of Scientific Biography
     Wolfram Research
     ScienceWorld.wolfram.com
        http://scienceworld.wolfram.com/biography/Euler.html

   from The Wikipedia Project
     Wikipedia The Free Encyclopedia
        http://en.wikipedia.org/wiki/Leonhard_Euler

send comments to Thomas M. Green c/o CCC Math Dept. hwalters@contracosta.cc.ca.us