2.1 Königsberg bridge problem (Ch. 2.1)

FIGURE 2.1: Leonhard Euler’s drawing of the seven bridges in Königsberg, Image credit: beanz Magazine

The above image is from beanz Magazine.

The challenge: Are you able to wall across all the seven bridges but cross each bridge only once? The starting and ending point is not specified.

Before reading on, I highly recommend you to try this exercise on mathsisfun.com by yourself. Getting the answer from others won’t help you learn it at the deepest level.

---

Solution to this challenge: if a path exists which allows a person to cross all the bridges but walk across each bridge only once, which is called a “Euler Path,” the number of nodes having an odd number of bridges should be either zero or two. When there are two nodes having an odd number of bridges, i.e., having an odd degree (a point we’ll learn later), one of the two nodes should be the starting point and the other the end point.

This remarkable discovery by Euler led to the development of a new branch in mathematics: graph theory.