Leonhard Euler and the Königsberg Bridge Problem: Leading To Topology and Graph Theory

By Preeti Juturu

7 min readSep 7, 2016

The Königsberg bridge problem is a recreational mathematical puzzle set in the old Prussian city of Königsberg (now Kaliningrad, Russia). For the longest time, the problem was an unsolvable mystery. Leonhard Euler’s ultimate resolution of the puzzle, however, ultimately led to the accidental development of topology and graph theory. The question is: how exactly DID he solve it? More importantly, what are topology and graph theory?

In the early 18th century, the citizens of Königsberg spent their days walking on an intricate arrangement of bridges across the waters of the Pregolya River, which surrounded two central land masses connected by a bridge. The first landmass (an island) was connected by four bridges, with two bridges connecting the lower bank, and two bridges connecting the upper bank. The other landmass, which split the Pregel into two branches, was connected to the lower and upper bank by two bridges, with one other bridge connecting both landmasses together. In total, there were seven bridges. According to folklore, a question arose: could a citizen take a walk through the town in such a way that each bridge would be crossed exactly once?

In 1735, Swiss mathematician Leonhard Euler presented a solution to this problem: such a walk was impossible. Euler recognized that in order to succeed, a traveller in the middle of the journey must enter a land mass via one bridge and leave by another, so that land mass must have an even number of connecting bridges. Furthermore, if the traveller at the start of the journey leaves one land mass, a single bridge will suffice. Upon completing the journey, the traveller will again require a single bridge to reach the ending point of the journey. The starting and ending points are then allowed to have an odd number of bridges. However, if the starting and ending point are to be the same land mass, then that land mass (as well as all other land masses) must have an even number of connecting bridges. The walk was therefore impossible.

It would be nearly 150 years before mathematicians could picture the Königsberg bridge problem as a graph consisting of nodes representing the landmasses (vertices), and arcs representing the bridges (edges). In modern graph theory, a Eulerian path traverses each edge of a graph once and only once. Thus, Euler’s assertion that a graph possessing such a path has at most two vertices of odd degree ended up becoming the first theorem in graph theory.

Euler described his work as geometria situs — the “geometry of position”. His work on this problem and some of his later work led directly to the fundamental ideas of combinatorial topology, which 19th-century mathematicians referred to as analysis situs — the “analysis of position”. Graph theory and topology, both emerging from Euler’s work, are now major areas of mathematical research.

In mathematics and computer science, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A “graph”, within this context, is made up of vertices and lines that connect them. A graph may be undirected (meaning that there is no distinction between the two vertices associated with each edge) or its edges may be directed from one vertex to another.

Topology is the study of geometric properties and spatial relations unaffected by the continuous change of shape and/or size of figures.

In graph theory, a graph bears no relation to the graphs that chart data (ex. the progress of the stock market). In graph theory, a “graph” is a collection of dots that may or may not be connected to each other by lines. It doesn’t matter how big the dots are, how long the lines are, or whether the lines are straight, curved, or squiggly. The “dots” don’t even have to be round.

Topology, in essence, is just comparing shapes. It is the mathematical and systematic study of the properties that are preserved through deformations, twistings, and stretchings of objects. For example, a circle is topographically equivalent to an ellipse. It is all but a matter of perspective (literally).

Examples of Graph Theory and Topology in Mathematics

First Theorem of Graph Theory (thanks Euler):

The weird looking E is a Greek letter called sigma. It is a symbol of a sum.
deg v is a shorthand way of saying the degree of a vertex in a graph.
The letter i which is a subscript of the v in “deg v” tells us which vertex is being referred to. The subscript i is related to the statement i=1 because it appears beneath the sigma.
The statement i=1 that appears beneath the sigma means that when you start adding up the sums of vertices, you should start with the first one.
The letter p is the letter that graph theorists use to represent the number of vertices in a graph. The number that p actually stands for at a given moment depends on the graph that you are studying.
The p above the sigma is a partner to the i = 1. i = 1 says to begin with 1, and p means to end with p. Since we are adding up degrees of vertices, “from i = 1 to p” means that we add up the degrees of all the vertices.
The q represents the number of edges in a graph. The number that q actually stands for will be different for different graphs.
2q means “2 times q”.

So, as a translation, the equation above reads:

“The sum of the degrees of all the vertices in a graph is equal to twice the number of edges.”

Topology:

Ever hear of a Möbius Loop — a one sided, one edged surface? Give a strip of paper a half-twist, then tape the ends together. It’s called a “Möbius strip”. Cool Fact: If an ant were to crawl along the length of this strip, it would return to its starting point having traversed the entire length of the strip (on both sides of the original paper) without ever crossing an edge. It’s one side and one boundary, with delightful properties dear to mathematicians (apparently). What an interesting finding in mathematics!

Above is an example of a Möbius strip. It may be simple, but it is actually extremely complex! Source

In 1882, Felix Klein imagined sewing two Möbius Loops together to create a single sided bottle with no boundary. The Klein Bottle is a mathematical joke because the inside is on the outside; it contains itself. Just as it’s about to enclose space like a regular bottle, it curves back with a twist so the inner face merges with the outer face. It can be cut in half along its length to make two Möbius strips, but can also be cut into a single Möbius strip.

I guess you could say that the Klein bottle is full of itself.

Now contrast this with a corked bottle — say, an apple cider bottle. It has two sides: inside and outside. You can’t get from one to the other without opening it up from the top. Once uncorked, it has a lip which separates the inside from the outside. An uncorked bottle is topologically equivalent to a disc … it has two sides, separated by an edge.

However, a Klein Bottle does not have an edge. It’s boundary-free, and an ant can walk along the entire surface without ever crossing an edge (similarly to a Möbius strip).

Here are the parametric equations, that define the surface of a Klein Bottle.:
x = cos(u)*(cos(u/2)*(sqrt_2+cos(v))+(sin(u/2)*sin(v)*cos(v)))
y = sin(u)*(cos(u/2)*(sqrt_2+cos(v))+(sin(u/2)*sin(v)*cos(v)))
z = -1*sin(u/2)*(sqrt_2+cos(v))+cos(u/2)*sin(v)*cos(v)

The Klein Bottle is definitely a Riemannian manifold…

Wormholes!

In physics and science fiction, a wormhole (better known as a Einstein-Rosen Bridge) is a hypothetical topological feature of spacetime that would fundamentally behave as a ‘shortcut’ through space and time. In essence, you could travel back and forth in time. Although they are very popular in science fiction, there is no actual evidence that they exist.

As a visualisation, consider spacetime as a two-dimensional (2-D) surface. Now, if we ‘fold’ this surface, it allows us to picture a wormhole ‘bridge’. A wormhole has at least two ‘mouths’ that are connected by a ‘throat’. If the wormhole is traversable, then matter can ‘travel’ from one mouth to the other via the throat.

Leonhard Euler and the Königsberg Bridge Problem: Leading To Topology and Graph Theory

By Preeti Juturu

Examples of Graph Theory and Topology in Mathematics

Topology:

Wormholes!

Sources:

Written by Preeti Juturu