The Seven Bridges of Königsberg

Definition In the eighteenth century the river Pregel divided the city of Königsberg, then in Prussia and now Kaliningrad in Russia, into four land regions. Call the island in the river $A$ and the two banks $B$ and $C$, and call the land to the east, between two branches of the river, $D$. Two bridges joined $A$ with $B$, two joined $A$ with $C$, and one bridge joined $D$ with each of $A$, $B$ and $C$, seven bridges in all. The puzzle asks for a walk that crosses every bridge exactly once. The walk may start and finish in any regions, the same one or two different ones, and it may pass through a region as often as it likes, but it may cross the water only by the bridges, and every crossing goes all the way over. The answer is that no such walk exists. Take a region where the walk neither starts nor finishes. Each of its bridges is crossed exactly once, either to arrive or to leave. Every arrival there is followed by a departure and every departure follows an arrival, each on its own bridge, so its bridges are used in pairs and their number would have to be even. Only the start and the finish can have an odd number of bridges, so at most two regions can. In Königsberg all four do, five for $A$ and three each for $B$, $C$ and $D$. Leonhard Euler gave this argument in the 1730s, and it is usually counted as the beginning of graph theory.

Definition A graph consists of points called vertices and of edges, where each edge joins two different vertices. On this page two vertices may be joined by more than one edge, just as two bridges can join the same two regions, and such edges count separately. Some books call this a multigraph and keep the word graph for the case of at most one edge per pair. A walk in a graph is a list $v_0, e_1, v_1, e_2, \ldots, e_k, v_k$ of vertices and edges in which each edge $e_i$ joins $v_{i-1}$ and $v_i$, for $i = 1, \ldots, k$, so it moves from vertex to vertex along edges. A graph is connected when any two of its vertices are joined by some walk. Graph theory is the branch of mathematics that studies graphs. Only which vertices each edge joins matters, not where the vertices are drawn or how long or how curved the edges are.

Definition The degree of a vertex is the number of edges that meet it. Each edge joining it to another vertex counts once, so two edges to the same neighbor count twice. A vertex of degree $0$ is called isolated, and a vertex is called odd or even according to its degree. Each edge has two ends, so adding the degrees of all the vertices counts every edge exactly twice. For a graph with $m$ edges whose vertices have degrees $d_1, d_2, \ldots, d_n$,

This is called the handshake lemma. The even degrees add up to an even number, so the odd degrees must also add up to an even number, which happens only when there is an even number of them. Every graph therefore has an even number of odd vertices.

Definition A trail is a walk that never uses the same edge twice, though it may pass through the same vertex several times. An Eulerian path, also called an Euler trail, is a trail that uses every edge of the graph exactly once. Some books reserve the name for a trail whose two ends are different. Euler’s theorem says when one exists. Let a graph have at least one edge, and suppose that any two of its vertices of positive degree are joined by a walk, so that the graph is connected once its isolated vertices are ignored. Then the graph has an Eulerian path exactly when it has $0$ or $2$ odd vertices. With $2$ odd vertices, every Eulerian path starts at one of them and ends at the other. With none, every Eulerian path ends at the vertex where it started. The degree condition is needed because each pass of a trail through a vertex uses one edge to arrive and another to leave, so at every vertex other than the two ends of the trail, the trail’s edges come in pairs. If the trail uses every edge, each vertex other than its ends therefore has even degree, its two ends have odd degree when they are different vertices, and every degree is even when the trail ends where it began. Connectivity is needed because a walk can never get from one part of a graph to another part that no edge joins it to.

Definition An Eulerian circuit is an Eulerian path that ends at the vertex where it started. Under the same conditions as in Euler’s theorem, at least one edge and every two vertices of positive degree joined by a walk, a graph has an Eulerian circuit exactly when every vertex has even degree, and then a circuit can start at any vertex of positive degree. Such a circuit can be built step by step, a method known as Hierholzer’s algorithm. Start at any vertex of positive degree and keep following unused edges. Whenever the walk enters a vertex other than the start, it has used an odd number of that vertex’s edges, so an unused one remains to leave by, and the walk can only get stuck back at the start, closing a loop. The loop used its edges in pairs at every vertex, so the unused edges still meet every vertex an even number of times. If some edges are still unused, connectivity guarantees that one of them meets a vertex of the loop. Walk a second loop of unused edges from there, which again can only close where it began, and insert it into the first loop at that vertex. Repeat until every edge is used. For a graph with exactly two odd vertices, add a temporary edge between them, which makes every degree even, build an Eulerian circuit, and delete the temporary edge from it. What is left is an Eulerian path from one odd vertex to the other.