Konigsberg Bridge Problem-
Konigsberg is the former name of a German city that is now in Russia.
The following picture shows the inner city of Konigsberg with the river Pregel which divides the city into four land areas A, B, C and D. In order to travel from one part of the city to another, there exist seven bridges as shown-
The problem states-
“Starting from any of the four land areas A, B, C, D, is it possible to cross each of the seven bridges exactly once and come back to the starting point without swimming across the river?”
In 1735, Swiss Mathematician Leon hard Euler solved this problem. He provided a solution to the problem and finally concluded that such a walk is not possible.
Euler represented the given situation using a graph as shown below-
Here, vertices represent the landmasses and edges represent the bridges.
Euler observed that when a vertex is visited during the process of tracing a graph, there must be one edge that enters into the vertex and another edge that leaves the vertex.
Therefore, the order of the vertex must be an even number.
Based on this observation, Euler discovered that it depends on the number of odd vertices present in the network whether any network is traversable or not.
Euler found that only those networks are traversable that have either-
- No odd vertices
(then any vertex may be the beginning and the same vertex will also be the ending point)
- Or exactly two odd vertices
(then one odd vertex will be the starting point and other odd vertex will be the ending point)
Since, the Konigsberg network has four odd vertices, therefore the network is not traversable.
It was finally concluded that the desired walking tour of Konigsberg is not possible.
If the citizens of Konigsberg decides to build an eighth bridge from A to C, then it would be possible walking without traversing any bridge twice because then there will be exactly two odd vertices. However, adding a ninth bridge will again make the walking tour once again impossible.
Get more notes and other study material of Graph Theory.
Watch video lectures by visiting our YouTube channel LearnVidFun.