Introducing Graph Theory - Bridges of Königsberg

Introducing Graph Theory - Bridges of Königsberg

Most of us would be remembering this classic problem, shared during our school days.

If not, these are the rules. Draw the above figure 1) without redrawing over same segments & 2) without taking off your pen from the paper.

There is a similar problem, introduced in the first half of 18th century. It is well know as the '7 Bridges of Königsberg'. Königsberg is a place in Prussia & there are two islands & mainlands connected by 7 bridges in the following fashion. The problem was to find an Eulerian (read as Oy-lerian) path.

Euler Path is a route that would cross each bridge once and only once. (If we introduce, an additional constraint, 'the walk need to be started and ended at the same spot', then the route is called as an Euler circuit.)

In 1735, a Swiss Mathematician, Leonhard Euler proved that there cannot be any Eulerian path in this graph. The idea behind this negative resolution is straight forward.

We can redraw the geographical diagram into a mathematical representation, called as a graph.

The land masses at which the bridges intersect are represented as nodes and the bridges which connect these nodes are represented as edges. Hence each edge is associated with two end points. The number of bridges connected to a node is called the order of a node. In this case there are 4 nodes. The orders of the nodes 1,2,3 & 4 are 3,5,3 &  3 respectively. Euler argued that

"For the existance of an Eulerian circuit in a graph with n nodes, all the n nodes should have an even order ." In simple words, there must be always an even number of bridges connected to a land division.

 

The idea behind this argument is simple. For a person to enter & leave a node through different bridges, there must be always an even number of bridge connected to that node. Or simply, for every p bridges along which a person enters a node, there must be a different set of p bridges along which he can exit.

"For the existance of an Eulerian path in a graph with n nodes, atleast n-2 vertices should have an even order."

Arguing as in the previous statement, the nodes at which the traveller starts and ends his journey can have an odd order. Thus all the remaining (n-2) nodes should have even order.

In the graph of Konigsberg, as all the 4 nodes have an odd order, there will not be any Eulerian path (or circuit). Going a step further

• We can create Eulerian paths by adding or removing atleast one bridge. There are, respectively, 6 & 7 different ways for adding & removing a single bridge in this manner.
• We can create Eulerian circuits by adding atleast 2 bridges (3 different ways), or removing 2 bridges (4 different ways) or by changing the position of a bride (7 different ways).

Coming back to the first question. Can you solve it now??