Euler approached this problem by collapsing areas of land separated by the river into points, which he labelled with capital letters. Modern graph theorists call these vertices, and have gone on to represent them and bridges graphically.
For Konigsberg, let us represent land with red dots and bridges with black curves, or arcs:
Thus, in its stripped down version,
the seven bridges problem looks like this:
The problem now becomes one of drawing this picture without retracing any
line and without picking your pencil up off the paper. Consider this: all
four of the vertices in the above picture have an odd number of arcs
connected to them. Take one of these vertices, say one of the ones with
three arcs connected to it. Say you're going along, trying to trace the
above figure out without picking up your pencil. The first time you get to
this vertex, you can leave by another arc. But the next time you arrive, you
can't. So you'd better be through drawing the figure when you get there!
Alternatively, you could start at that vertex, and then arrive and leave
later. But then you can't come back. Thus every vertex with an odd number of
arcs attached to it has to be either the beginning or the end of your
pencilpath. So you can only have up to two 'odd' vertices! Thus it is
impossible to draw the above picture in one pencil stroke without
retracing.
The Generalization to Graph Theory
Euler went on to generalize this mode of thinking, laying a foundation for graph theory. Using modern vocabulary, we make the following definitions and prove a theorem:
Definition: A network is a figure made up of points (vertices) connected by nonintersecting curves (arcs).
Definition: A vertex is called odd if it has an odd number of arcs leading to it, other
wise it is called even.
Definition: An Euler path is a continuous path that passes through every arc once and only once.
Theorem: If a network has more than two odd vertices, it does not have an Euler path.
Euler also proved this:
Theorem: If a network has two or zero odd vertices, it has at least one Euler path. In particular, if a network has exactly two odd vertices, then its Euler paths can only start on one of the odd vertices, and end on the other.
Problems
Problem 4:
For each of the networks below, determine whether it has an Euler path. If it does, find one.


figure 1

figure 2



figure 3

figure 4



figure 5

figure 6

Solution

Problem 5:
Without finding (or trying to find) an Euler path, determine whether the
network below has any Euler paths.

figure 7

Solution

to the Bridges of
Konigsberg
to the Value of Pi
