Bridges of Konigsberg

Graph Theory

Many of you may have come across the rightmost shape in a puzzle. You are expected to draw the above shape without taking the pencil off the paper and without retracing any line. Many would have realized that the task is impossible unless you do some tricky moves like folding the paper.

But basic ideas in a field called Graph Theory, helps us understand the puzzle in a deeper way. Let me try to explain the solution in simple words.

The above figure consists of some nodes and lines. At any node a number of lines meet. You can think of the lines as roads and nodes as road junctions.

If a node has 2 lines, we can think of coming to the node with one line and leaving the node with the other line. This is true if the node has an even number of lines meeting at the node.

But if the node has only 1 node then you can only come into the node and there is no way out from the node. Hence it is an "ending" node. It can also be thought of as a "starting" node. This is true if the node has an odd number of lines meeting at the node.

If a figure has 2 "odd" nodes, then any one of them can be the "startin" node and the other the "ending" node. This means we can start drawing from any one of them and end at the other.

Hence if there are more than 2 "odd" nodes then the drawing cannot be done. If all the nodes in a figure are "even" nodes, the figure can be drawn starting & ending in a number of nodes.

The above figure has 4 nodes with 5 lines i.e 4 "odd" nodes. Hence this figure cannot be drawn within the stipulated conditions.

If any of the semi circles is removed, it removes 2 of the "odd" nodes leaving only 2 out of the 4. Then the figure can be drawn.

Today Graph Theory is a full-fledged branch of mathematics and is used in many disciplines to show the relations (lines) between objects or ideas (nodes). The structure of a website can be shown as a graph.

The germ of the idea of Graph Theory came out of a puzzle which was called Bridges of Konigsburg. It was essentially about 2 islands in the city of Konigsburg being connected by 7 bridges. The challenge was to start from a point, cross each of the 7 bridges just once and come back to the starting point.

Bridges of Konigsburg

The people of Königsberg tried walking different paths, but no one could find a way to cross each bridge exactly once and return to their starting point. This wasn’t just a casual puzzle; it was a real challenge that intrigued the residents of the city. The puzzle became so famous that it reached the ears of the Swiss mathematician Leonhard Euler, who decided to tackle it.

In 1736, Leonard Euler wrote the first paper on Graph Theory, based on the above puzzle. It is one of the instances of an entire branch of math being the outcome of a puzzle.

By representing the bridges with lines and the landing points as nodes, he demonstrated the power of math to represent a real-life problem with a symbolic one, allowing us to focus only on the essential relations.

Another parallel idea is the representation of a real-life problem with a symbolic expression or equation. The equation removes all information extraneous to the problem and helps us focus on the essential relations.