The Bridges of Konigsberg // 41

¨

¨ The Bridges of Konigsberg Occasionally, a simple puzzle starts a whole new area of mathematics. Such occurrences are rare, but I can think of at least three. The most famous such puzzle is known as the Bridges of Konigsberg, which led Leonhard Euler* to invent a branch of

¨

¨ graph theory in 1735. Konigsberg, which was in Prussia in those days, straddled the river Pregel. There were two islands, connected to the banks and each other by seven bridges. The puzzle was: is it possible to find a path that crosses each bridge exactly once?

Euler's

diagram

of the

Konigsberg

¨

bridges.

Euler solved the puzzle by proving that no solution exists. More generally, he gave a criterion for any problem of this kind to have a solution, and observed that it did not apply to this particular example. He pointed out that the exact geometry is irrelevant ­ what matters is how everything is connected. So the puzzle reduces to a simple network of dots, joined by lines, here shown superimposed on the map. Each dot corresponds to one connected piece of land, and two dots are joined by lines if there is a bridge linking the corresponding pieces of land.

* It is mandatory to point out that his name is pronounced `oiler',

not `yooler'. Numerous oil-based puns then become equally

mandatory, but I won't mention any. 42 // The Bridges of Konigsberg

¨

Turning the

Konigsberg

¨

bridges into

a network.

So we get four dots, A, B, C and D, and seven edges, a, b, c, d, e, f and g, one for each bridge. The puzzle now simplifies to this: is it possible to find a path through the network that includes each line exactly once? You might like to experiment before reading on.

To work out when a solution exists, Euler distinguished two kinds of path. An open tour starts and ends at different dots; a closed tour starts and ends at the same dot. He proved that for this particular network, neither kind of tour exists. The main theoretical idea is the valency of each dot: how many lines meet there. For instance, 5 lines meet at dot A, so the valency of A is 5.

Suppose that a closed tour exists on some network. Whenever one of the lines in the tour enters a dot, then the next line must exit from that dot. So, if a closed tour is possible, the number of lines at any given dot must be even: every dot must have even

¨ valency. This already rules out any closed tour of the Konigsberg bridges, because that network has three dots of valency 3 and one of valency 5 ­ all odd numbers.

A similar criterion works for open tours, but now there must be exactly two dots of odd valency: one at the start of the tour,

¨ the other at its end. The Konigsberg diagram has four vertices with odd valency, so there is no open tour either.

Euler also proved that these conditions are sufficient for a tour to exist, provided the diagram is connected ­ any two dots must be linked by some path. Euler's proof of this is quite

two page view?

all devices