The city of Königsberg is set on the sides of Pregel river and two islands. The riverbanks are connected by seven bridges (see the picture). The problem is to determine, whether it is possible to walk through the city, crossing each bridge exactly once, and return to the same place.
The problem of seven bridges is similar to the children game of drawing the house in one line.
Solution
Solution to this problem was presented by Leonhard Euler in 1736 and it is considered as a foundation stone of the graph theory.
Theorem: Undirected graph can be covered by one trail if and only if it is connected and is a Euler graph (i.e. all its vertices are of even degree).
Theorem: Let be an undirected graph, which has
vertices of odd degree (
), then its every minimal coverage consists of
open trails, out of which every connects a pair of vertices of odd degree.
From these two theorems arises that if want to draw an image using one line (or walk through Königsberg) and return to the place, where we have started, then there must come out even count of lines (edges) from every node (vertex). If the graph does not meet this condition, then we need at least trails, because these are the places where we start to draw the trail and where we stop.
On the schema we can see now that is not not possible to go through all Königsberg bridges, visit each once, and return to the original place. It is impossible to solve this problem even without the condition stating that we must return to the original place, because at least two trails are needed.
Sources
- KOLÁŘ, Josef. Teoretická informatika. 2. ed. Praha : Česká informatická společnost, 2004. 205 p. ISBN 80-900853-8-5.