The Königsberg bridges
In the old city of Königsberg (now Kaliningrad), it was a popular Sunday pastime to try to cross all seven bridges in the town exactly once while returning to the same starting point. No-one seemed able to do it. When Euler tackled the problem in 1736, he thought of it this way: let each bridge be represented by a line (or edge) and each land area by a point (or vertex) to produce a figure with seven edges and four vertices.
He noticed that each vertex is odd, that is, is connected by an odd number of edges. This suggested that if you start your tour at any vertex, you could not end it there. After considering a simple case, Euler was able to prove that
• in a graph, the total number of odd vertices is even (check this);
• a graph can be traversed (every edge is visited exactly once) if and only if there are either no odd vertices, or exactly two odd vertices. If there are no odd vertices, the traversal ends at the starting point.
Since the graph for the bridges has more than two odd vertices (it has four), then no traversing path is possible. Thus Euler showed why the Königsbergers were unsuccessful in their quest: the problem is not solvable.
