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.
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.
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
mathsbyagirl 