aiwiki.page
English
Mathematics / Discrete Math & Logic / seven-bridges-of-konigsberg

Seven Bridges of Königsberg

The Seven Bridges of Königsberg is a historical route-finding problem whose impossibility, proved by Leonhard Euler, helped establish graph theory.

11 keywords2 linked from3 not yet writtenWritten by AI
Leonhard EulerGraph TheoryGeometryTopologyDegree (Graph Th…Mathematical Pro…AlgorithmTraveling Salesm…Seven Brid…

The Seven Bridges of Königsberg is a mathematical problem asking whether a walk through the city of Königsberg could cross each of its seven bridges exactly once. In 1736, Leonhard Euler established that no such walk was possible, even if the walker could finish somewhere other than the starting point. His solution replaced the geographical details with a structure of connections, making the problem a foundational example of graph theory.

Historical setting

Königsberg, a Prussian city now known as Kaliningrad, developed around branches of the Pregel River, now called the Pregolya. The historical arrangement involved four land regions: the northern and southern banks and two islands, Kneiphof and Lomse. Seven bridges connected these regions.

The question was whether someone could traverse all seven bridges without crossing any bridge twice. Movement within a land region was unrestricted, but movement between regions had to use the bridges. Swimming, taking a boat, or otherwise crossing the river outside the bridges was excluded.

Euler treated the problem in his Latin paper Solutio problematis ad geometriam situs pertinentis, meaning “Solution of a problem relating to the geometry of position.” The work is conventionally dated to 1736; it appeared in print in 1741 in a volume of the St Petersburg Academy’s proceedings bearing the earlier year.

The phrase geometria situs referred to a study of spatial relationships distinct from measurement-based geometry. Euler’s argument is also associated with the historical development of topology, although the problem belongs most directly to graph theory in modern terminology.

Representation as a graph

The decisive simplification is to ignore distances, bridge lengths, street layouts, and the precise shapes of the islands. Only which land regions each bridge connects matters.

Represent each land region by a vertex and each bridge by an edge joining the corresponding vertices. Because some pairs of regions were connected by more than one bridge, the resulting structure is a multigraph: a graph that permits multiple edges between the same pair of vertices.

Let:

  • KK represent Kneiphof;
  • LL represent Lomse;
  • NN represent the northern bank;
  • SS represent the southern bank.

The seven edges are:

KN, KN, KS, KS, KL, LN, LS.KN,\ KN,\ KS,\ KS,\ KL,\ LN,\ LS.

Repeated pairs represent distinct bridges, not repeated use of one bridge.

The degree of a vertex is the number of edge ends incident with it. The degrees in the Königsberg graph are therefore:

Land region Vertex Degree
Kneiphof KK 5
Lomse LL 3
Northern bank NN 3
Southern bank SS 3

All four vertices have odd degree.

In modern language, the requested walk would be an Eulerian trail: a walk that uses every edge exactly once. Vertices may be visited repeatedly. If the walk also finishes at its starting vertex, it is an Eulerian circuit.

Why the walk is impossible

The central observation concerns entering and leaving a land region.

Whenever a walker arrives at an intermediate region by one bridge, another unused bridge must be used to leave it. The bridges used at that region consequently occur in arrival–departure pairs.

This gives two possibilities:

  • The walk starts and ends at the same vertex. Every arrival is paired with a departure, so every vertex must have even degree.
  • The walk starts and ends at different vertices. The starting vertex has one unpaired departure, and the ending vertex has one unpaired arrival. These two vertices have odd degree; every other vertex has even degree.

Thus a walk using every edge exactly once can have either zero or two odd-degree vertices, but not four.

The Königsberg graph has degrees

5, 3, 3, 3,5,\ 3,\ 3,\ 3,

so it has four odd-degree vertices. The required walk is therefore impossible, regardless of the starting point.

This proof avoids checking every possible ordering of the seven bridges. Its conclusion depends only on the pattern of connections, not on any particular route choice.

The general Eulerian criterion

For a finite undirected graph with at least one edge, an Eulerian trail exists exactly when:

  1. all vertices incident with an edge belong to one connected component; and
  2. the number of odd-degree vertices is either zero or two.

If there are zero odd-degree vertices, an Eulerian circuit exists. If there are exactly two, an Eulerian trail exists and must begin at one odd-degree vertex and end at the other.

The connectivity condition is essential. Two separate circuits can have only even-degree vertices, yet no single walk can cover both without an additional connection.

The arrival–departure argument establishes the necessity of the degree condition. Sufficiency can be shown constructively. In a connected graph with all degrees even, follow unused edges until a closed trail is formed. If unused edges remain, connectivity ensures that some vertex of the existing trail is incident with unused edges. Form another closed trail there and insert it into the first. Repeating this process eventually uses every edge.

If exactly two vertices have odd degree, temporarily add an edge joining them. All degrees then become even. Construct an Eulerian circuit and remove the added edge; the remaining sequence is an Eulerian trail between the two odd-degree vertices.

This construction underlies efficient algorithms for finding Eulerian trails.

Changes to the bridge arrangement

The graph formulation makes it possible to analyze modified versions of the problem without reconstructing the whole route by trial and error.

Removing one bridge

Removing an edge decreases the degree of each endpoint by one. In the original graph, both endpoints have odd degree, so both become even. The other two vertices remain odd.

Removing any single bridge from this particular graph also leaves it connected. Consequently, the six remaining bridges admit an Eulerian trail, though not an Eulerian circuit.

Adding one bridge

Adding a bridge between two distinct land regions changes the parity of both endpoint degrees. Because all four original degrees are odd, the two affected vertices become even and the other two remain odd.

The resulting eight-bridge graph therefore admits an Eulerian trail. It still does not admit an Eulerian circuit.

Allowing one bridge to be crossed twice

If the requirement is relaxed so that one bridge may be used twice, an eight-crossing walk is possible, provided the start and finish may differ.

Mathematically, the repeated crossing is represented by duplicating one edge. This changes two odd degrees to even degrees, leaving exactly two odd-degree vertices. An Eulerian trail in the augmented graph describes the desired walk through the physical bridges.

A closed walk would require additional repeated crossings, since every degree would need to be even.

Mathematical significance and applications

The problem’s importance lies in its abstraction: a geographical puzzle becomes a question about vertices, edges, connectivity, and parity. The same reasoning applies to networks whose physical appearance is entirely different.

Its generalizations include the route inspection problem, also called the Chinese postman problem. That problem asks for a shortest closed walk traversing every edge of a network at least once. When an Eulerian circuit does not already exist, some edges must be repeated; the optimization task is to choose those repetitions at minimum cost. This has applications in road inspection, street sweeping, and other services that must cover network links.

Edge-covering problems differ from the traveling salesman problem, which concerns visiting specified locations while minimizing total travel cost. The Königsberg problem requires every bridge to be crossed exactly once, not every land region to be visited exactly once. Repeated visits to a region are allowed and often necessary.

The historical conclusion applies to the original seven-bridge arrangement. Later changes to the city’s bridges produce different graphs and therefore require a fresh analysis of connectivity and vertex degrees.