Can You Draw It Without Lifting Your Pencil? Euler Paths
In the 1700s, the city of Konigsberg (now called Kaliningrad) had seven bridges connecting four pieces of land along a river. Townspeople loved to argue about a puzzle: could you take a walk through the city crossing every single bridge exactly once, without recrossing any of them? People tried for years and always got stuck. In 1735, a mathematician named Leonhard Euler proved it was impossible - and in doing so, he invented an entirely new branch of math called graph theory.
What You'll Learn
- The real puzzle that started graph theory - How to turn a map into dots and lines called a graph - Euler's rule for knowing whether a path is possible before you even try - How to test any shape using the pencil-lifting trick
Meet the Puzzle That Started It All
Konigsberg's seven bridges connected two riverbanks and two islands. Walkers wanted a route that crossed each bridge exactly once and could start and end anywhere. Euler realized the exact shape of the land and bridges did not matter - only how the pieces of land connected to each other. So he simplified the whole city into a picture: four dots for the four landmasses, and seven lines for the seven bridges connecting them.
Turning Bridges Into Dots and Lines
In graph theory, dots are called vertices and lines connecting them are called edges. Euler counted how many edges touched each vertex - this number is called the vertex's degree. He noticed that every one of Konigsberg's four landmasses had an odd degree (three vertices had degree 3, one had degree 5). Euler proved that a walk crossing every edge exactly once - now called an Euler path - is only possible if a graph has exactly zero or exactly two vertices with an odd degree. Konigsberg had four odd vertices, so the walk was mathematically impossible, no matter how cleverly you tried.
You can test any drawing yourself: count how many lines meet at each corner (its degree). If the shape has zero or exactly two corners with an odd number of lines meeting there, you can trace the whole thing without lifting your pencil or retracing a line. Any more than two odd corners, and it is impossible - just like Konigsberg's bridges.
Try It Yourself: Simple Shapes
A square with both diagonals drawn in has four corners, each with degree 3 (odd) - four odd vertices means it fails the pencil test, just like Konigsberg. A simple envelope shape (a square with a triangle roof and both roof lines meeting the top corners) has exactly two odd vertices at the bottom corners, so it passes - you can trace it in one stroke starting at either bottom corner. A five-pointed star drawn without lifting your pencil works because every point has degree 2, which is even, so the whole star has zero odd vertices.
Why did Leonhard Euler conclude the Konigsberg bridge walk was impossible?
A shape has exactly two corners where an odd number of lines meet, and the rest have an even number. What does this tell you?
Design and Test Your Own Graph
Draw three different shapes made of connected lines (like a bowtie, a house outline, or a triangle grid). For each shape, count the degree of every vertex and predict whether it has an Euler path. Then actually try tracing each one without lifting your pencil to check your prediction, and record which shapes worked and why.
Want to keep learning?
Sign up for free to access the full curriculum — all subjects, all ages.
Start Learning Free