Seven Bridges of Königsberg

The problem (1736). Königsberg sat on both banks of the Pregel river, with two islands connected by seven bridges. Can one walk through the city crossing every bridge exactly once?

Euler proved: no — and in doing so founded graph theory.

Euler’s argument

Reduce the city to a graph: the four land masses are vertices, the seven bridges are edges.

        A
       /|\
      / | \
     C--B--C          (multi-edges: two bridges between some pairs)
      \ | /
        D

The degrees are $3, 3, 3, 5$ — four odd-degree vertices.

Every time the walk enters a land mass it must leave again, so each visit uses two bridges. A land mass with odd degree must therefore be the start or the end of the walk.

A walk has only two endpoints, so at most two vertices may have odd degree.

Königsberg has four. Impossible. ∎

The general theorem

For a connected graph (ignoring isolated vertices):

	Condition
Eulerian circuit (closed)	every vertex has even degree
Eulerian path (open)	exactly two vertices have odd degree
Neither	four or more odd-degree vertices

By the handshake lemma the number of odd-degree vertices is always even, so “exactly two” is the only open case. See Eulerian Path and Circuit.

For directed graphs: a circuit requires $de g^{+} = de g^{-}$ everywhere; a path allows one vertex with $de g^{+} - de g^{-} = 1$ (the start) and one with the reverse.

Constructing the tour

Hierholzer’s algorithm finds an Eulerian circuit in $O (E)$ : walk until stuck, then splice in detours from vertices with unused edges.

// iterative Hierholzer with a per-vertex edge pointer
while (!st.empty()) {
    int u = st.back();
    while (it[u] < (int)adj[u].size() && used[adj[u][it[u]].id]) it[u]++;
    if (it[u] == (int)adj[u].size()) { circuit.push_back(u); st.pop_back(); }
    else { auto [v, id] = adj[u][it[u]++]; used[id] = true; st.push_back(v); }
}

The it[] pointer is essential — without it the algorithm degrades to $O (V E)$ .

What Euler’s argument teaches

It is the archetype of an invariant / parity impossibility proof:

Identify a quantity every legal move preserves or changes predictably (here: each visit consumes two edge-ends).
Show the goal state is incompatible with it.
Conclude impossibility — without any search.

The same move proves the 15-puzzle unsolvable for odd permutations, the mutilated chessboard untileable, and the closed knight’s tour impossible on odd boards.

The modern descendants

Problem	Relation
Eulerian path	the direct generalisation, $O (E)$
Chinese postman	traverse every edge at least once, minimising distance — pair up odd vertices with a min-weight matching
De Bruijn sequences	an Eulerian circuit in the de Bruijn graph
Genome assembly	Eulerian path in a de Bruijn graph of reads
Hamiltonian path	the vertex analogue — NP-complete, in sharp contrast
Route inspection, snow ploughing, mail delivery	Chinese postman in practice

The Eulerian/Hamiltonian contrast is one of the most instructive pairs in the subject: “use every edge once” has a local degree characterisation and a linear algorithm; “use every vertex once” has neither.

The Chinese postman, concretely

If the graph is Eulerian, the answer is the total edge weight. Otherwise, find the odd-degree vertices (an even number, say $2 k$ ), compute shortest paths among them, find a minimum-weight perfect matching on those $2 k$ , and duplicate the matched paths:

$answer = \sum_{e} w_{e} + min perfect matching among odd vertices .$

With $2 k \leq 16$ , a bitmask DP does the matching; otherwise Blossom.

The historical note

Euler’s 1736 paper is generally regarded as the first work in graph theory and in topology — he explicitly noted that the answer depends only on the connection structure, not on distances or geometry. Two of Königsberg’s bridges were destroyed in 1944, and today the city (Kaliningrad) has five bridges and exactly two odd-degree vertices, so an Eulerian path now exists.

See also: Eulerian Path · Hierholzer · Parity Arguments

whoashish's cp notes

Directory