Introduction to Graph Theory - Part 1

The Königsberg Bridge Problem: How a Simple Puzzle Changed Mathematics

In the 18th century, the city of Königsberg (now Kaliningrad, Russia) faced a curious challenge: could someone take a walk through the city that crossed each of its seven bridges exactly once? The city was divided by the Pregel River, which created four distinct landmasses connected by these seven bridges. The problem intrigued locals and sparked plenty of attempts, but no one could figure out a solution.

Enter Leonhard Euler, a brilliant Swiss mathematician who looked at the problem in a completely new way. His work didn’t just answer the question; it laid the foundation for an entirely new branch of mathematics called graph theory, which remains essential to this day.

The Puzzle: Seven Bridges, One Big Question

Königsberg had seven bridges connecting its landmasses, and the goal was to find a way to cross all of them without going over any one bridge twice. For years, the question went unanswered, leaving many people frustrated.

That’s when Euler decided to take a different approach. Instead of thinking about the geography of the city, he looked at the problem in a more abstract way—focusing on the connections between the landmasses. This new perspective would eventually lead him to a groundbreaking discovery.

Euler’s Insight: Turning Bridges into Graphs

Euler realized that he didn’t need to worry about the physical layout of the city. Instead, he could represent the problem with simple nodes (for the landmasses) and edges (for the bridges connecting them). This made it much easier to analyze and led Euler to an important insight:

For it to be possible to walk across all the bridges exactly once, there had to be specific properties in the graph. In fact, Euler discovered that for such a walk, the number of edges connected to each node (the landmasses) must be even—with the exception of at most two nodes, which could have an odd number of edges.

When Euler applied this rule to Königsberg, he found a problem: all four of the landmasses had an odd number of bridges connecting to them. So, the conclusion was clear: a walk crossing every bridge exactly once simply isn’t possible.

Why It’s Important: The Birth of Graph Theory

Euler’s solution to the Königsberg Bridge Problem didn’t just answer the riddle—it gave birth to graph theory, a field of mathematics that is now used in countless applications. From computer networks to social media, transportation planning, and even biology, graph theory helps us understand the connections that drive complex systems.

What began as a fun local puzzle about bridges grew into a revolutionary mathematical concept that shapes modern life today. Euler didn’t just solve the problem—he changed the way we think about networks and connections.

In the following, we will look at the basics of graph theory and learn where it is used.