Bridges of Königsberg

From ProofWiki
Jump to navigation Jump to search

Problem

Through the city of Königsberg flowed the Pregel River. In this river were two large islands, which were part of the city.

Joining the mainland either side of the river and those two islands there stood seven bridges.

Konigsberg bridges.png

It was a popular exercise among the citizens to take a pleasure stroll across the bridges.

The question naturally arose: was it possible to cross each bridge once and once only during the course of a single walk?

More to the point: could this be done such that the walkers end up back at their starting point?


Solution

The shape of the land and the positions of the bridges are irrelevant.

What is important is the relationships between the land and the bridges.

We can represent each of the landmasses as the vertices and the bridges as the edges of a multigraph:

KonigsbergBridgesGraph.png

The question now evolves into: does this graph allow the construction of an Eulerian circuit, or failing that, an Eulerian trail?


It can be seen that this is a graph in which there are four vertices, each of which is odd.

From Characteristics of Eulerian Graph, it is clear that the walkers can not cross all the bridges once each and return to their starting point, as all the vertices would need to be even for that.


From Characteristics of Traversable Graph, it also follows that this graph is not traversable, as it has more than two odd vertices.


The answer to both questions is, therefore: No.

$\blacksquare$


Also see

This problem does not relate, in any way, to graph theoretic bridges.


Historical Note

The solution of the Bridges of Königsberg problem, in a rather different form, was first given by Leonhard Euler in his $1736$ paper Solutio problematis ad geometriam situs pertinentis.

This is widely considered as the first ever paper in the field of graph theory.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Bridges_of_Königsberg&oldid=593131"