The Bridges of Königsberg was the name of a math puzzle that remained unsolved for hundreds of years. The city of Königsberg, now known as Kaliningrad (in Russia) was built across the river Pregel and on two islands that were on the river. Seven bridges connected the islands and two shores to each other. It was held that the inhabitants of the city would walk through the entire city on Sunday afternoons. Somewhere along the line, a mathematical puzzle was born: was it possible to pass through the city by crossing every bridge once and only once, and if so, what path must one take?

Here is what the city looked like in a rough diagram form. Note that double vertical bars (||) and equal signs (=) are bridges. Single vertical bars (|), the plus sign (+) and the dashes (-) show where the edge of the land is. I have also labelled the city's four parts to explain the solution later.

      P A R T   A
----------------------
     ||   ||      ||
     ||   ||      ||
   +---------+  +----+
   | P A R T |==|PART|
   |    B    |  |  C |
   +---------+  +----+
     ||   ||      ||
     ||   ||      ||
----------------------
      P A R T    D

Try it for yourself and see if you can solve it. It's really not that hard, once you start thinking the right way.

The solution: it isn't possible to traverse all seven bridges without crossing over any one of them more than once.

Proof of the solution: any island or shore (which is be called a vertex in some forms of mathematics) that has an odd number of bridges connected to it must be an endpoint of the journey. Why? Well, quite simply, you must either start there or end there. Using Part B as an example, consider two situations: either our path starts at B or starts elsewhere. If it starts at B, it goes out along one bridge, comes through another, and leaves from the third bridge. Thus, B is an endpoint. If the path starts somewhere other than B, it must go through B along one bridge, come back along another, and then come back again along the last bridge. But now, all the bridges are used up and so the path must end there. Thus, B is an endpoint again. It is a small mental jump to generalize that this must be true for any odd number of bridges leaving an island or shore. But, look again at the diagram. Parts A, B, C, and D all have an odd number of bridges connecting them. No valid path can have more than 2 endpoints... thus, the challenge is impossible!

The solution was first discovered by Leonhard Euler in a famous 1736 paper. By solving the Bridges of Königsberg, Euler not only immortalized the problem, but he created graph theory (alternately called network theory and topology in different contexts).

PS: Thanks to barbie for pointing out I originally had only 6 bridges drawn out (I forgot to connect B and C). So go upvote barbie. Thanks!

PPS: I didn't realize there was another node about this. However, I ask the editors to let this node stay because (a) it provides the correct spelling of the term and (b) it provides a proof of the solution.

Log in or register to write something here or to contact authors.