The Seven Bridges of Konigsberg

Konigsberg Map | Konigsberg Bridges | Konigsberg Bridges Alone | Konigsberg Graph | Konigsberg Graph Alone

The original problem was to find a walk through the city that would cross each bridge once and only once, with the following rules:

• the islands could not be reached by any route other than the bridges,
• every bridge must have been crossed completely every time, and
• the walk need not start and end at the same spot.

which can now be rephrased in terms of the graph as:

• Can we construct a path that travels along each edge once and only once?

The answer lies in the idea that if we travel to a vertex, we must leave the vertex. So all vertices between the beginning and final vertex must have an even number of edges incident.

The beginning and final vertex can have an odd number of edges incident, but if we wish to end at the place we started (a circuit rather than a path), then all vertices in the graph must have an even number of edges incident.