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.
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
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 it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Rooted Trees.
Least You Need to Know: Rooted TreesRelated lessons
Keep going with nearby lessons in the same topic.