SME
Discrete Mathematics · Problem type
Euler circuit, Euler path or neither
Use this for “A connected graph has degrees 3, 3, 2, 2. Does it have an Euler path or an Euler circuit?”
Sort
Which does the graph have?
Tap a card, then tap its group.
Count the odd degrees: 0 gives a circuit, 2 a path, more gives neither.
Assumptions
•
Each graph is connected; each vertex shows its degree, the number of edge ends it meets.
•
An Euler path uses every edge exactly once; an Euler circuit also ends where it starts.
•
Every graph has an even number of odd-degree vertices, since the degree sum is 2E.
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.