The Königsberg Problem and its relation to graph theory and beyond.

Königsberg, an old city in Prussia, founded in 1255 (Presently Kaliningrad, Russia) had a River passing through it, the River Pregel, which the city divided into a tuning fork shape(see Fig 1). In the early 18th century the citizens of the city roamed through the intricate array of the seven bridges which connected various parts of the city across the Pregel River. These bridges lead to the development of a new mathematical problem called the Königsberg Bridge Problem.

Fig 1: The city of Königsberg dividing the River Pregel into a tuning-fork like shape. There are 7 bridges connecting various parts of the city across the Pregel River.

The Königsberg Bridge Problem and the Euler Analysis:

The Königsberg Bridge Problem was a fun mathematical puzzle that led to many developments in field of mathematics. Here’s how the problem goes:

Is there a path you can take across the Königsberg city by crossing each and every one of the 7 bridges exactly once?

Think about this problem for a minute. It might seem simple at first glance, and it is. But, I highly recommend getting a pen and paper and try out this problem for yourself before reading further.

Fig 2: An easier to understand version of the Königsberg Bridges
CC BY-SA 3.0, Link

Leonhard Euler (1707-1783), a famous mathematician, who lived in nearby St. Petersburg (he has so many things named after him) found a new way of analysing the Königsberg Problem.

Fig 3: Portrait of Leonard Euler

Euler analysed the problem by taking each landmass as a single point, formally called a node. He could do this because movement inside the landmass is irrelevant. The bridges are considered as lines, formally called edges. The length and shape of the edges didn’t matter as it only signifies as connection between two nodes.

Fig 4: The Eulerian Analysis of the Königsberg problem using nodes and edges. The blue circles represent the nodes, the landmass – and the black lines represent the edges, the bridges connecting the landmasses.
(CC BY-SA 3.0, Link)

The Analysis:
If a person enters a landmass through a bridge then he must leave the landmass through a different bridge. In other words the number of bridges leading into a landmass must equal the number of bridges leaving the landmass. Unless, the landmass serves as an endpoint for the path. What this means is that since, the number of bridges leading up to a landmass must equal the number leaving it, in turn implying that the total number of bridges connected to a landmass is even. (n+n = 2n)

Fig 5: An image of one of the Königsberg bridges crossing the Pregel River.

Note: Whether a bridge is considered as leading up to a landmass or leaving a landmass is arbitrary because you can move both sides on a bridge. You arbitrarily chose the direction you want to go in.

Graph Theory

In more mathematical terms, the number of edges connected to a node is called the “degree” of the node. This way of using nodes and edges is called a “graph”, not the kind of graphs you know about like a bar graph, line graph etc. This graph is different, it is essentially “a network of nodes and edges connected to each other.” It is a way of representing how objects are connected without actually worrying about the distance between them. Essentially, the position (i.e the location) is important not the distance. So Euler called this as “The Geometry of Position”.

So, as explained earlier since the number of bridges connected to a bridge should be even, unless it is the end point, this implies that:

“For there to be a path which traverses all the edges exactly once, there can be at most two nodes of odd degree, because there can be at most two end points.”

The above statement was called the Eulerian Assertion, using this assertion it isn’t too hard to prove why no path along the Königsberg is possible wherein all the 4 landmasses have odd degree, implying that no path along these bridges traversing each bridge once is impossible.

Graph Theory and Topology, both born from this Eulerian Assertion, are both areas where extensive research happens to this day. We are going to discuss one of these areas, Graph Theory, the study of graphs. The Eulerian Assertion, after being proved, ended up as the first theorem in Graph theory.

In real-life, these graphs are very useful, for example while drawing a map for the train routes and stations in the city, the distance between the stations is less important, but the connection between the stations is.

Fig 6: The map of the London underground. This map is particularly useful for seeing the connections between the stations, but it isn’t very useful to actually plan a trip because the distances between the stations isn’t actually scaled so many stations are either very close or very far in this map than they actually are in real life.
Taken from tfl.gov.uk

Graph theory has evolved and it now has applications in computer science, chemistry, operations research and even social science. But, we will get to those applications later.

Formal Definitions of a Graph & its types :

A graph as discussed before is a set of nodes and edges, hence it can be represented as:
A graph G is an ordered pair of nodes and edges- (N, E) where N and E can be further defined as :-
N, a set of nodes
E ⊆ {{x, y}⎮x, y ∈ N and x≠y }, i.e a set of edges which are unordered pairs(sets) of two distinct nodes.
This kind of mathematical representation is called a simple graph, where two nodes can be joined by at most one edge.

If a graph is permitted to have multiple edges(or parallel edges) i.e more than one edge having the same end point, then such a graph is called a multi-graph.

There are two types of multi-graphs:
One wherein the edges have no identity, meaning that the identity of the edge is solely defined by the vertices it’s connected to, In this case “multiple edges” means that the same edge occurs many times between two vertices.
Another type is wherein the edges have its own identity, meaning that the edge is considered as a primitive object like the node, so if two or more edges connect two vertices then the edges are considered different.

Fig 7a: A Simple Graph wherein two nodes are joined by at most one edge.
Fig 7b: A multi-graph where two nodes can be joined by more than one edge.

Mathematical Defintion of Multi-graphs:

Multi-graph where Edges have no identity- An ordered pair (N, E) where,
N is a set of nodes
E is a multi-set of nodes, called edges. A “multi-set” allows multiple instances of elements, unlike a normal set where multiple instances of the same elements is prohibited. This basically means the same node can appear multiple times in the set of nodes (the edges). So the same edge connects between two nodes multiple times.

Multi-graph where Edges have their own identity- An ordered pair (N, E, ɸ ) where,
N is a set of nodes
E is a set of edges and ɸ, is where it gets interesting-
ɸ : E → {{x, y}: x, y N}, this means assigning each edge its own set of two nodes. So each edge is assigned two node meaning two different edges can be assigned to the same two nodes, so two or more different edges can appear between two nodes. If you look carefully you can observe that since you are assigning each edge its own set of nodes and an edge cannot be assigned more than one set of nodes it in turn eliminates the case where the edges have no identity.
In the ɸ definition, you might notice that I have not mentioned x≠y, this is because there is a thing called loops in a graph, where a node is connected back to itself. Some authors accept loops in a graph, while others call them as pseudo graphs implying that loops are not acceptable in a multigraph.

Fig 8: A multi pseudo graph with multiple loops(in blue) and also more than one connection (in red) between two vertices.
0x24a537r9CC BY-SA 3.0

There is a graph much more complicated than this, called a hyper graph wherein an edge can join any number of vertices 2, 3, 4 or more, but this is out of reach of this particular blog.

Whenever appropriate you can even assign direction to an edge, representing the direction you can move on the edge, called a directed graph or digraph.

Fig 9: A directed graph or digraph

These kinds of graphs are particularly useful for airplane routes where sometimes you can go from one airport to another in only direction and other times when airplanes go to and fro from one airport to another, where it the plane route can be easily graphed by using parallel edges with opposite directions. In Fig 8, between the middle node and the right node you can see a connection to both sides ⟷ which is a short form for representing two parallel nodes of opposite direction.

A directed multigraph, a multi-digraph as discussed earlier is basically where parallel edges between two nodes are allowed, but the edges have direction.

The mathematical definition: A multi-digraph is an ordered 4-tuple (N, E, S, T):
where,
N is a set of nodes,
E is a set of edges,
S : E→ N, assigning each edge its source node,
T : E → N, assigning each edge its target node.

Paths and Circuits

There is another important characteristic in a graph, a path, any route along the edges of a graph. It could be along only one edge joining two nodes or along multiple edges joining multiple nodes. A Eulerian Path (or Eulerian Trial) is a path (also called a trail) in a graph that moves along every edge exactly once (allows revisiting of nodes) basically, the Königsberg problem. A Eulerian Circuit (or Eulerian Cycle) is a Eulerian Path which starts and ends on the same node and the graph which contains it, is called Eulerian Graph. Every vertex in a Eulerian graph should have even degree, because the Euler’s Assertion says there can be at most two nodes with odd degree but that is true because we have considered 2 end points in a graph. But, in this case there are no end points, the path starts and ends at the same vertex so there is no end point, so there can’t be any node with odd degree in a Eulerian Graph.

Fig 10: Follow along the edges of this graph, in alphabetical order(A –> K) to get an Eulerian circuit. If you observe closely you will notice that each node has an even degree ensuing the existence of a Eulerian Circuit.

The Hamiltonian Circuit:

In 1857, the Irish Mathematician Rowan Hamilton made a puzzle (the Icosian game) which he later sold to a manufacturer for 25€. The game involved finding a special kind of path, a Hamiltonian circuit along the sides of a Dodecahedron, a platonic solid (already discussed in quasicrystals). A Hamiltonian Circuit is basically finding a path which visits each node exactly once and starts and ends at the same point, contrary to a Eulerian Circuit where each edge is visited exactly once.

Fig 11: A Hamiltonian circuit along six nodes.
Janusz.c, CC BY-SA 3.0,
Fig 12: The Platonic Solids

All the platonic solids have a Hamiltonian circuit, which was also proved, but the proof is beyond this blog. Let us a discuss the most popular Hamiltonian Circuit: A Hamiltonian Circuit along a Dodecahedron.

Fig 13: One possible Hamiltonian circuit along a Dodecahedron
cmglee, Arne Nordmann, CC BY-SA 4.0,
Fig 14: A 2D reconstruction of the Hamiltonian Circuit along the Dodecahedron.
Christoph Sommer, CC BY-SA 3.0

The Hamiltonian Circuits are a lot more challenging to characterise than eulerian Circuits and I will not go into detail about it as it involves a lot of math.

Applications of Graph Theory:

Ah yes, finally, the applications of this highly elaborate theory:

In Computer Science, graphs are very helpful to show the flow of communication, data organisation, the flow of computation, Neural Networks etc. (A Neural Network is basically a weighted graph, wherein we assign a weight/ a number to each node which is exactly a Neural Network)
It even has applications in Physics, Chemistry, Biology, Mathematics, GPS’s, Search engines, social sciences and even linguistics.

Graph Theory has many useful real-life applications, it is not just an intellectual ornament.

2 thoughts on “The Königsberg Problem and its relation to graph theory and beyond.

  1. A very clear explanation of your thoughts. Beautifully presented article. Well done Abhiram. Keep it up.

Leave a Reply

%d bloggers like this: