Problem History
The Seven Bridges of Königsberg was a popular brainteaser in which the solver was tasked with navigating the shores and islands of the Pregel River, crossing each bridge exactly once. The mathematician Leonhard Euler first gave a solution in 1736. Here is his account of the problem, as translated by Struik, accompanied by the diagram from his original paper:
The problem, supposedly quite well known, was as follows: At Königsberg in Prussia there is an island A, called "der Kneiphof," and the river surrounding it is divided into two branches as can be seen in Figure 1. Over the branches of this river lead seven bridges, a, b, c, d, e, f, and g. Now the question is whether one can plan a walk so as to cross each bridge once and not more than once. I was told that some deny this possibility, others are doubtful, but that nobody affirms it.
While a modern graph diagram did not appear in Euler’s 1736 paper, the reasoning he used when formulating his solution to the problem based on the structure of his diagram was the seed for the modern field of graph theory. A path through the vertices of a graph that traverses every edge exactly once is now known as an Eulerian path in his honor.
Mathematical Theory
Graphs
While we may be more used to thinking of graphs as curves plotted against a set of axes on a Cartesian plane, in graph theory, a graph is a geometric figure consisting of nodes with segments connecting some of them. In this context, a node is called a vertex and a segment connecting two vertices is called an edge. If two vertices share an edge, they are said to be adjacent.
Graphs are useful in thinking about problems concerning objects and relationships between them. In the case of the Bridges of Königsberg, the objects are plots of land separated by water and the relationship between them is connection by a bridge. Other examples of graphs include:
- Social media: users are vertices, two users are adjacent if they are friends or follow each other
- Highways systems: cities are vertices, two cities are adjacent if directly connected by a highway
- Computer networks: computers are vertices, network wires are edges
- Ecosystems: lifeforms are the vertices, two lifeforms are adjacent if one will eat the other
- Subway systems: stops are vertices, two stops are adjacent if they are one stop away from each other along some subway line
- Airlines: airports are vertices, two airports are adjacent if there is a direct flight from one to the other
In a directed graph (or digraph), a relationship need not be reciprocal or symmetric. For example, on Facebook, being friends with another user means they are also friends with you, so that relationship is reciprocal and edges don’t require any direction; on Twitter or Instagram, one user can follow another without being followed back.
In a multigraph, a relationship can be repeated. For example, with airlines we could ask whether there is a direct flight and draw or not draw an edge, accordingly. However, we could also track all of the direct flights from one airport to another, drawing one edge for each. This could be helpful for getting a sense of how many people we could move in a given day.
Graph theory remains a very active area of mathematical research. It contains a lot of problems that are easy to state but very difficult to solve.
Eulerian paths
A key concept Euler noted when studying the bridges was the number of edges adjacent to a given vertex, which we call the degree of the vertex.
Degree gives a way to discuss how a vertex may be passed through when traversing the graph, since each edge must be used to enter or exit the vertex. Since a vertex of odd degree must then correspond to
enter, exit, enter, exit, ... , exit, enter
or
exit, enter, exit, enter, ... , enter, exit
an odd degree vertex must then be a place where an Eulerian path begins or ends, respectively. Graphs for which it is possible to trace an Eulerian path thus have at most two vertices of odd degree.
Degree gives a nice entrypoint for carrying out computations and numerically reasoning with graphs. For example, every edge is connected to two vertices, so if we sum the degrees of all vertices in a graph, we end up with the same count we would obtain by counting the number of edges and then doubling it:
deg(v1) + deg(v2) +...+ deg(vn) = 2e
This means that the sum of the degrees is an even number, so the number of odd-degree vertices must be even for any graph! A graph with an Eulerian path must then have only vertices of even degree or exactly two vertices of odd degree.
Another useful concept in graph theory is connectedness. If there is a route from one vertex to another, regardless of the number of edges that must be traversed, we say those two vertices are connected by a path. A graph is connected if there is a path from each vertex to every other vertex.
If one wants to find an Eulerian path, many algorithms for doing so can be found in terms of connectedness. For example, Fleury’s algorithm constructs an Eulerian path as follows:
- Start at a vertex of odd degree, if one exists, or any other vertex, otherwise.
- Find an edge adjacent to this vertex where deleting it would leave the graph connected. Travel along this edge and delete it.
- At each next vertex, carry out the same edge selection process for the new graph with deleted edges, always choosing an edge where deletion won’t disconnect the graph, traveling along it, and deleting it. (If there is ever a vertex with no edge whose deletion would leave the graph connected, then choose the only edge adjacent to that vertex and proceed as usual.)
After following this algorithm, every edge will be visited once.
Eulerian paths have applications to postal, garbage collection, and street sweeping routes, DNA fragment assembly, and circuit design.
For more details on the history and theory behind our Königsberg puzzle, see here!