In 1736 the people of Königsberg asked whether they could walk across each of their seven bridges exactly once. Euler answered with an argument about degrees, and graph theory began. The question is about trails: routes that never reuse an edge.
Key idea
An Euler circuit is a closed trail that uses every edge exactly once; an Euler path uses every edge exactly once but may end somewhere else. A connected graph has an Euler circuit exactly when every vertex has even degree, and an Euler path (but no circuit) exactly when exactly two vertices have odd degree; the path must start at one of them and end at the other.
Why it works
Each time a trail passes through a vertex, it arrives on one edge and leaves on another, using up two edges there. So at every vertex other than the start and end, the edges come in pairs: the degree is even. In a closed trail the start is also passed through, so every degree is even. For a path, the start and end each have one unpaired edge, so they, and only they, have odd degree. The converse (even degrees really do guarantee a circuit in a connected graph) is proved by building the circuit: start anywhere, walk until you return, and splice in detours through any unused edges.
Worked examples
Worked example: Königsberg
The four land areas have degrees $5, 3, 3, 3$. Is there an Euler path or circuit?
- Four vertices have odd degree.
- A circuit needs zero odd vertices; a path needs exactly two. Four is neither.
Answer: Neither
Worked example: A house shape
A square $ABCD$ (edges $AB, BC, CD, DA$) has a roof: a vertex $E$ joined to $A$ and $B$. Does it have an Euler path? Where must it start?
- Degrees: $A$ and $B$ have $3$; $C$, $D$, $E$ have $2$. Exactly two odd vertices.
- So an Euler path exists, from $A$ to $B$ (or the reverse), but no circuit.
- One path: $A \to E \to B \to A \to D \to C \to B$.
Answer: Yes, starting at $A$ or $B$
Worked example: Complete graphs
For which $n$ does $K_{n}$ have an Euler circuit?
- Every vertex of $K_{n}$ has degree $n - 1$, and $K_{n}$ is connected.
- All degrees are even exactly when $n$ is odd.
Answer: Odd $n$
Common mistake
Confusing Euler with Hamilton, or starting at an even vertex. Euler routes use every edge once; Hamilton routes, in the next lesson, visit every vertex once. And when exactly two vertices are odd, an Euler path that starts at an even vertex gets stuck. Check: count the odd vertices first; they tell you whether a route exists and where it must start.