Bridges of Knigsberg & Eulerian circuits

Authors Avatar

Bridges of Königsberg & Eulerian circuits

The ‘Königsberg bridge’ problem is based on a city that had seven bridges, which connected two islands. The problem was to find whether there is any way to cross over all seven bridges once without turning back onto a bridge that has already been crossed. Figure 1 shows what the bridges and river looked like when Eular was around.

Fig. 1

In, 1736 Euler the problem using what people now believe as the start of graph theory. He proved that there were no solutions at all to this problem hence you cannot cross all the bridges exactly once. The way Euler solved it was by thinking of the river and bridges in terms of graph theory. This was achieved by removing anything unnecessary to the problem and so therefore ended up drawing a picture primarily consisting of points that represented the islands and separate lines showing the bridges that connected the islands. Figure 2 shows the picture of what Eular might have drawn up.

Join now!

Fig. 2

As you can see the problem now looks much simpler and one could attempt to solve by just using a pencil and going around the lines looking for a solution but to find a systematic approach to is incredibly tedious laborious. Euler devised a new notion; degree of nodes. The Degree of Node is the number of connections or  the node has to other nodes. Euler said that any graph can be fully crossed with each edge crossing exactly once if it had, zero or exactly two nodes with odd degrees. ...

This is a preview of the whole essay