|KONIGSBERG'S BRIDGES||Contact Us At Contra Costa College||Math Dept. Home Page|
Euler's Konigsberg's Bridges Problem
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!
|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).
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.
In the Great Hall of Mathematical Learning there are 12 rooms
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.
("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".
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
from Eric Weisstein's World of Scientific Biography
from The Wikipedia Project
Wikipedia The Free Encyclopedia
send comments to Thomas M. Green c/o CCC Math Dept.
Top of document
Contra Costa College