Tuesday, October 8, 2013

The Bridges of Königsberg (Urban Math)

Cambridge, October 8, 2013

Many cities have rivers running along or through them. Sooner or later most of them have built bridges crossing their rivers. And in turn, those bridges have inspired countless artists and writers. From the top of my head I can think of Art Crane's exquisite poem about the Brooklyn Bridge and I'm that sure you'll be able to think of many other great examples. But how many examples of bridges that inspired mathematicians can you think of?

In 1735, the great Swiss mathematician Leonhard Euler solved the riddle known as the "Seven Bridges of Königsberg", demonstrating the first theorem of graph theory and establishing the foundations of topology.

The city of Königsberg in Easter Prussia (now Kaliningrad, Russia) is traversed by the Pregel River and includes two islands. At the time, the city and the islands were connected by seven bridges. Euler managed to demonstrate that it was not possible to devise a route through the city crossing all seven bridges once and only once. In mathematical terms, a trail that visits every edge (the bridges in Euler's example) of a graph (the path) exactly once, is referred to as an "Eulerian path", and one that accomplishes that beginning and ending at the same place as an "Eulerian circuit".

And no, the Königsberg Bridges graph is not Eulerian. But go ahead, pick a city with bridges and give it a try.