Graphs / Euler Trails
Least You Need to Know: Euler Trails and Cycles
Euler questions ask whether you can use every edge exactly once. The degree pattern tells you the answer quickly.
The least you need to know
- A connected graph has an Euler cycle exactly when every vertex has even degree.
- A connected graph has an Euler trail but not a cycle exactly when it has two odd-degree vertices.
- Degree counts edges touching a vertex.
- You must use every edge exactly once, not every vertex exactly once.
- Connectivity matters for Euler questions.
Key notation
deg(v)
degree of vertex v
trail
walk using no edge more than once
cycle
closed walk
Tiny worked example
- Suppose a connected graph has vertices of degrees `2, 4, 3, 3`.
- Exactly two vertices are odd.
- So the graph has an Euler trail but not an Euler cycle.
Common mistakes
- Students often answer a Hamilton question when asked an Euler question.
- Students sometimes ignore disconnected components.
- Students often count vertices instead of odd-degree vertices.
How to recognize this kind of problem
- The question asks whether every edge can be used exactly once.
- The graph diagram or data includes vertex degrees.
- You are asked to distinguish trail versus cycle.