Seven Bridges of Königsberg

The Seven Bridges of Königsberg problem asks if it is possible to find a closed walk in a graph that uses every edge exactly once. Euler represented the landmasses as vertices and the bridges as edges. He proved that such a walk (an Eulerian circuit) exists if and only if every vertex in the graph has even degree (an even number of edges connected to it). In the Königsberg graph, all four vertices have odd degree, so an Eulerian circuit is impossible.

Important properties

• A graph has an Eulerian circuit if and only if every vertex has even degree and the graph is connected.

• If exactly two vertices have odd degree, an Eulerian path (not a circuit) exists, starting and ending at those vertices.

• The Königsberg problem led to the creation of graph theory.