The Eulerian Problem

Graph Theory · Axiom Academy

Can you walk across every bridge in a city exactly once? In 1736, the city of Königsberg (modern-day Kaliningrad) had a famous puzzle that puzzled its citizens. Start at any land area and try to cross all 7 bridges exactly once. Click the bridges in the order you want to cross them. Euler realized that the exact shapes and sizes don't matter. What matters is the connections! The Secret: Count the Connections Euler discovered that the solution depends on how many edges meet at each vertex. This is called the degree of a vertex. This graph has exactly 2 vertices with odd degree. Can you find an Eulerian path? Euler showed that complex real-world problems can be solved by focusing on structure and relationships, not physical details. Today, graph theory is everywhere: social networks, GPS navigation, computer networks, molecular chemistry, and even solving sudoku puzzles! Euler's theorem elegantly solves an entire class of problems with a single criterion: count the odd-degree vertices. Zero or two? Solvable. Otherwise? Impossible.

This is the written version of the interactive lesson above. See the full Graph Theory course.