Euler's Theorem for Eulerian Paths
You'll learn the exact condition that determines when a graph has an Eulerian path—a single continuous walk that uses every edge exactly once.
The Core Idea
In the previous lesson, you learned that a connected graph has an Eulerian circuit (a closed loop using every edge once) if and only if every vertex has even degree. But what if we want a path that doesn't need to return to its starting point?
Euler's Theorem for Eulerian Paths states that a connected graph has an Eulerian path if and only if it has exactly zero or two vertices of odd degree.
Let's break this down:
- Zero vertices of odd degree: This means all vertices have even degree, so the graph actually has an Eulerian circuit (which is also technically a path).
- Exactly two vertices of odd degree: The Eulerian path must start at one odd-degree vertex and end at the other. Every edge gets used exactly once, but the path is not a closed loop.
Why This Works
Think of traversing edges like drawing without lifting your pencil. At every vertex you visit in the middle of your journey, you must enter and exit—requiring an even number of edges. The only exceptions are your starting and ending points:
- The starting vertex has one extra edge you exit on (odd degree)
- The ending vertex has one extra edge you enter on (odd degree)
If you have more than two odd-degree vertices, it's impossible to create a single continuous path through all edges—you'd run out of "exits" at some vertices and have leftover edges at others.
Key Takeaway: A connected graph has an Eulerian path if and only if it has exactly 0 or 2 vertices of odd degree; if 2, the path starts and ends at those two vertices.