A Stroll, Seven Bridges, and a Mathematical Revolution
The big question of this module. Can you walk a city crossing each bridge exactly once? And how do you prove that it is impossible?
Königsberg, 1736: seven bridges and a Sunday walk
The story does not start in a laboratory but on the streets of Königsberg, a city in 18th-century Prussia. It was a city of thinkers, most famously Immanuel Kant, but the puzzle that would change mathematics belonged to everyone.
The city was built around two islands in the Pregel River, which were connected to the mainland and each other by seven different bridges. During their Sunday strolls, the citizens enjoyed a challenge:
Is it possible to design a walking route that crosses each of the seven bridges in the city exactly once and returns to the starting point?
Try it yourself in the city below. Click a landmass to place your pencil, then click a bridge to cross it. The tracer will never let you cross the same bridge twice. You’ll hit the exact same wall the citizens did—you’ll get stuck somewhere with a bridge still unused. Then the last two steps stop reporting that you failed and start showing you why you always would.
What you just saw is the reason, drawn rather than argued. No one in Königsberg had that reason. They only had the first half—no one could find a route, and even worse, no one could prove that one didn’t exist. The problem eventually reached the mathematician Leonhard Euler. His goal was not to have the answer, but to have the reason in a form that would work for any city, any number of islands, and any number of bridges.
Read Euler’s solution, but before you do so, think like a mathematician for an hour. This is how discovery happens, and I strongly recommend that you work through the pen-and-paper worksheet before you go further. It hands you a campus, not a city: seven footbridges you can tour, an eighth that ruins it, and a ledger to keep until you can tell the two apart without walking either. As you work through it, ask yourself:
- What information is essential? The length of a bridge? The size of an island?
- What are the fundamental constraints of the problem?
- How can you move from “I can’t find a route” to “a route cannot exist”?
Euler throws away the map
Euler’s genius was the realization that most of the information on the map was a distraction. He performed a radical act of simplification, a process we now call abstraction.
He stripped the problem down to its bare bones:
- He turned each of the four landmasses into a simple dot (a node).
- He turned each of the seven bridges into a simple line (an edge) connecting the dots.
This was no mere sketch; it was a new mathematical object. Euler invented the graph (or network). He created a language to speak about relationships and connectivity, rather than numbers or shapes.
What a graph is, formally
Formally, a graph is a pair
G = (V, E)
where V is a set of nodes (also called vertices), and E is a set of edges, each of which is a pair of nodes. In the case of Königsberg, V has four elements (the two banks and the two islands), and E has seven elements.
Everything else in this course is built on these two sets. Notice what the definition does not contain: no coordinates, no distances, no shapes.
It is useful to mention two features of Königsberg at this point, because the definition above implicitly allows both of them.
Parallel edges. In Königsberg, there are two pairs of bridges connecting the same two landmasses. Bridges a and b both go from island A to the south bank B, while bridges c and d both go from A to the north bank C. Because we count each bridge separately, the set E contains the pair (A,B) two times and the pair (A,C) two times. Graphs that allow such parallel edges are called multigraphs. If we were to combine each pair into a single edge, we would be solving a different puzzle with a different answer. This is why the multiplicity matters.
Self-loops. An edge can also connect a node to itself, which is called a self-loop. While self-loops are not present in the Königsberg problem, they are frequent in real networks (a paper citing itself, or a bank lending money to itself). Self-loops add 2 to the number of edges at the node, because both ends of the edge connect to it. This convention keeps the even/odd discussion in the next section working: a self-loop represents one incoming and one outgoing edge, which does not flip the odd-even state of a node.
Leonhard Euler (1707–1783) is one of the most prolific mathematicians in history. Despite losing his eyesight, he produced nearly half of his lifelong work completely blind.
From a walk to a proof: the idea of degree
This simplified representation allowed Euler to stop thinking about walking and start thinking about rules. He focused on the nodes and asked a key question: how does a journey through a node work?
Suppose you are on a walk and cross a bridge every time you reach a landmass. Every time you leave a landmass, you cross another. Therefore, at any landmass other than the start or the end of your journey, you must use bridges in pairs: one “in” and one “out.”
Count the number of bridges attached to each landmass. This number is called the degree of the node.
The degree of a node is the number of edges connected to it. Degree is one of the most basic properties of a node in a network.
- If a node has an even degree (2, 4, 6, …), you can always pass through it. Every “in” bridge has an “out” bridge.
- If a node has an odd degree (1, 3, 5, …), it must be special: the “in” and “out” bridges cannot all be paired up, one bridge is left over, and that leftover bridge means an odd-degree node must be the start or the end of your walk.
A journey has only one start and one end point. Therefore, if you can cross all bridges exactly once, there can be at most two nodes with an odd degree.
The verdict: all four landmasses are odd
Count the bridges at each node in Figure 1:
- C, the north bank: bridges c, d, g — degree 3 (odd)
- B, the south bank: bridges a, b, f — degree 3 (odd)
- A, the Kneiphof island: bridges a, b, c, d, e — degree 5 (odd)
- D, the east island: bridges e, f, g — degree 3 (odd)
All four landmasses have an odd degree, and such a journey allows at most two odd-degree nodes as start and end points. The walk the citizens asked for is mathematically impossible. Euler not only failed to find the walk but also proved, with logical certainty, that no such walk could exist.
A route that crosses every edge exactly once is called an Eulerian trail. A trail is a route with no repeated edges. A trail may pass through the same node more than once, and in Königsberg you are forced to do so. The full vocabulary is on the next page.
A graph has an Eulerian trail (a route crossing every edge exactly once) if and only if two things hold:
- The graph is connected, meaning that any node can reach any other node, and
- one of these holds:
- None of the nodes have an odd degree. In this case, the route can start and end at the same node, creating a closed loop called an Eulerian circuit.
- Exactly two nodes have odd degree. In this case, the route must start at one of them and end at the other.
The discussion above proves one direction: if such a route exists, there are at most two odd nodes. This direction is all the Königsberg problem needs, because its four odd nodes already rule out the possibility. The reverse direction — that these conditions are also sufficient, so that a route can actually be built whenever they are met — requires a short separate argument, sketched in the appendix.
You can watch that direction do its work before you read the argument. The graph below is not Königsberg: it has exactly two odd corners, so Euler’s condition promises a trail is in there somewhere. Step through and one gets built, edge by edge. Then the same graph is walked from an even corner and strands one edge short — not bad luck, but the two odd corners insisting on being the two ends. The last step hands you the pencil.
The bombs that changed the answer
There is an ironic ending to the story of the seven bridges. During World War II, Königsberg was subjected to a fierce bombing in which two of the seven bridges, b and d — one from each of the island’s two parallel pairs — were destroyed.
Now let’s recount the degree of each node, excluding b and d. A keeps a, c, e (degree 3), B keeps a, f (degree 2), C keeps c, g (degree 2), and D still has e, f, g (degree 3). Exactly two odd nodes remain. Therefore, there is a route that crosses all five surviving bridges, and it must start on one island and end on the other.
Note what that does not say. What the citizens asked for was a walk that returns to its starting point, and this requires that there are still no odd-degree nodes. The bombs made it possible to have a trail but not a circuit; the circuit is as impossible as it ever was. Two words that sound synonymous in English, trail and circuit, have different answers in the same city.
Euler’s solution was far more than fun trivia. It was the beginning of a new branch of science. The idea of abstracting systems into nodes and edges is how we understand our modern world, and every time you depend on a connected system, you benefit from Euler’s intellectual leap over a puzzle about a Sunday stroll.
What you can now do
- Turn a physical layout into nodes and edges, and defend what you threw away.
- Count the degree of each node and decide whether an Eulerian trail or circuit exists.
- Explain why “I could not find one” and “one cannot exist” are entirely different claims.
Next: Five Words You Will Use All Semester — walk, trail, path, circuit, cycle — plus the two objects the rest of the course leans on hardest, the adjacency matrix and the connected component. Then write the code on the hands-on page, and hand in the exercises.