MATHS BITE: The Bridges of Königsberg

In 1735, the city of Königsberg in Prussia (which is now Kaliningrad, Russia) was divided into four sections by the Pregel River. These four sections where connected by seven bridges.

Source: Wikipedia

The Königsberg bridge problem asked whether there was a walk through the city that would cross each bridge once and only once.

In 1736 Euler proved that this walk was not possible, achieving this by inventing a kind of diagram called a network, that is made up of vertices (dots where lines meet) and arcs (lines). His solution was presented to the St. Petersburg Academy in August 1735, and was published in the journal Commentarii academiae scientiarum Petropolitanae in 1741.

Screen Shot 2016-09-16 at 11.19.49 AM.png

Source: Wolfram MathWorld

This was a novel idea; Euler discovered that the physical positions of the sections do not matter, but rather it’s the connections made by the bridges that matters. Hence, by having this intuition Euler opened up a new branch of mathematics: graph theory. Euler describes how:

“. . . this type of solution bears little relationship to mathematics, and I do not understand why you expect a mathematician to produce it, rather than anyone else, for the solution is based on reason alone, and its discovery does not depend on any mathematical principle.”

So why is such a walk not possible?

Euler showed that the possibility of this walk existing – called a Eulerian path – is dependant on the  degrees of the nodes. The degree of a node is how many edges touch it. He found that the necessary condition for this walk to exist is that should have exactly 0 or 2 nodes with an odd degree.

As all four of the nodes in the network of Königsberg have an odd degree, the walk does not exist.

M x

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s