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.
บทเรียนถัดไปที่แนะนำ
เรียนต่อในหัวข้อนี้ด้วย Least You Need to Know: Rooted Trees
Least You Need to Know: Rooted Treesบทเรียนที่เกี่ยวข้อง
เรียนต่อด้วยบทเรียนใกล้เคียงในหัวข้อเดียวกัน