Eulerian Paths and Circuits: Definition and Motivation
What you'll learn: You'll discover what it means to traverse every edge of a graph exactly once, a problem famously inspired by the bridges of Königsberg.
The Core Idea
Imagine walking through a city trying to cross every bridge exactly once without repeating any bridge. This is the essence of an Eulerian path—a walk through a graph that traverses every edge exactly once. If your walk also ends where you started, you've completed an Eulerian circuit (or Eulerian cycle), which is a closed Eulerian path.
Why Does This Matter?
The concept originated with Leonhard Euler in 1736 when he solved the famous Königsberg bridge problem. The city had seven bridges connecting four land masses, and residents wondered if they could walk across each bridge exactly once. Euler proved it was impossible—and in doing so, founded graph theory!
Formal Definitions
- Eulerian Path: A path in a graph that uses every edge exactly once (vertices may be repeated, but edges cannot)
- Eulerian Circuit: An Eulerian path that starts and ends at the same vertex, forming a closed loop
Think of it like drawing a figure without lifting your pen and without retracing any line—except you can cross over points you've already visited, just not re-use edges.
Everyday Analogy
Consider a mail carrier who must walk every street (edge) in their route exactly once to deliver mail efficiently. An Eulerian path would be a perfect delivery route; an Eulerian circuit would let them return to the post office after covering all streets.
Key Takeaway: Eulerian paths traverse every edge exactly once; Eulerian circuits do the same but return to the starting vertex, forming a closed tour through all edges of a graph.