Throwback Fact of the Week - Seven Bridges of Königsberg - 7/17/14

Seven Bridges of Königsberg Problem

Königsberg was a city in Prussia, situated on the Pregel river. This river flowed through the town and created two large islands. These islands were connected to the mainland by 7 bridges, as depicted in the image below. 

Königsberg Bridges, image credit: Bogdan Giuşcă

The problem asked if it was possible to take a walk through town and cross over each bridge once and only once. Try it for yourself using the image above!

The answer to the question turns out to be "no" and a proof of this was published by Leonhard Euler in 1735. Euler's work laid the foundations of Graph Theory. Euler let each individual landmass represent a "vertex" (4 in all) and each bridge an "edge" (7 in all). The order of a vertex is the number of edges at that vertex. Euler showed that a graph such as this is only traversible if there are at most two vertices of odd order.

All four of the vertices in the Königsberg Bridge problem have odd order, and thus it is not possible to walk through town and cross each bridge only once.