Can you trace every edge of a graph exactly once without lifting your pen? If you can, you've found an Euler path. If you also finish back where you started, it's an Euler circuit. The whole topic is decided by counting how many vertices have an odd degree.
| Odd-degree vertices | Result | Where it starts & ends |
|---|---|---|
| 0 | Euler circuit | same vertex (a loop) |
| 2 | Euler path | at the two odd vertices |
| 4, 6, 8 β¦ | Neither | can't be done in one trip |
You can never have exactly 1, 3 or 5 odd vertices. The handshaking lemma makes the number of odd-degree vertices always even.
A planar graph can be drawn with no crossing edges. v = vertices, e = edges, f = faces (regions, including the big outer one). Rearrange for whichever is missing: f = 2 β v + e.
A road network has 6 intersections with degrees 4, 2, 4, 3, 3, 2. Can a maintenance vehicle drive every road exactly once?
β’ Count odd vertices, not even ones, that's the whole decision.
β’ For a 2-odd Euler path, you must start (or end) at an odd-degree vertex.
β’ "Circuit" means back to the start, "path" means finish somewhere else.
β’ Faces in Euler's formula include the outer region, it's easy to forget.
Left: a square, every vertex degree 2, so 0 odd, an Euler circuit. Right: a triangle with a tail, the two red vertices are odd (degree 3 and degree 1), so it's an Euler path that must start or end at a red one.
A square: 4 vertices, 4 edges, and 2 faces (the inside and the outer region). Check: v β e + f = 4 β 4 + 2 = 2 β.
Don't read yet, just have a go in your head:
Odd ones: 3 and 3. Count of odd = 2. So β Euler path, start at a degree-3 vertex.
Degrees 4, 2, 4, 3, 3, 2 β number of odd vertices = ? β result is ?
A graph has degrees 2, 4, 2, 4. Is it an Euler circuit, path, or neither? Check below.
A planar network has 9 vertices and 13 edges. How many faces (regions) does it create?
In one sentence, out loud: what do you count to decide if a graph has an Euler circuit, a path, or neither?