πŸ’‘
Learning My Way
Tutoring with a Twist
πŸ“… Exam
4 to 5 Nov 2026
Home β€Ί Networks & Decision Maths β€Ί Euler Paths & Circuits
Unit 4 Β· Networks

〰️ Euler Paths & Circuits

Can you trace every edge in a graph without lifting your pen? The answer depends entirely on counting odd-degree vertices, a simple rule with surprisingly powerful results.

πŸ”‘ Before this clicks: if any of these feel shaky, a 5-minute refresh makes this page way easier:
πŸ•ΈοΈ Graph Theory Basics

What even is this?

An Euler path traces every edge in a graph exactly once. An Euler circuit does the same and returns to where it started. These come up in scheduling, route planning, and inspections, any situation where you need to cover every connection without backtracking.

The entire topic comes down to one question: how many vertices have odd degree?

1
Traversability, The Core Idea

A graph is traversable if you can trace every edge exactly once without lifting your pen. The number of odd-degree vertices determines what kind of traversal is possible.

Odd-degree vertices What's possible Extra rule
0 Euler circuit, starts and ends at the same vertex Can start anywhere
2 Euler path, starts and ends at different vertices Must start at one of the two odd-degree vertices
4 or more Not traversable, cannot trace all edges once You would need to repeat some edges
You can never have exactly 1 odd-degree vertex. The Handshaking Lemma says the sum of all degrees is always even (= 2 Γ— edges), so the number of odd-degree vertices must always be even: 0, 2, 4, 6...
2
Euler Circuit vs Euler Path, Visualised
Euler Circuit, all even degrees
A B V C D d=2 d=2 d=4 d=2 d=2
0 odd-degree vertices β†’ Euler circuit βœ“
Euler Path, 2 odd-degree vertices
A B C D d=2 d=3 d=3 d=2 B and C are odd (red), start path here
2 odd-degree vertices β†’ Euler path (start at B or C)
3
Euler's Formula for Planar Graphs

A planar graph is one that can be drawn with no crossing edges. For any connected planar graph:

Euler's Formula (Planar Graphs) v βˆ’ e + f = 2
v = number of vertices  Β·  e = number of edges  Β·  f = number of faces (regions)

Faces include the outer unbounded region. When you draw a planar graph, it divides the plane into enclosed regions plus the infinite outer area, count them all as faces.
Example: A square (4 vertices, 4 edges as a cycle) has 2 faces: the inside of the square, and the outer region. Check: v βˆ’ e + f = 4 βˆ’ 4 + 2 = 2 βœ“
Rearrange to find any variable:
To find f:  f = 2 βˆ’ v + e   |   To find e:  e = v + f βˆ’ 2   |   To find v:  v = 2 + e βˆ’ f
4
Worked Examples
πŸ—ΊοΈ
Example A Β· Euler Circuit or Path?
A road network has 6 intersections. Their connection counts (degrees) are: 4, 2, 4, 3, 3, 2. Can a maintenance vehicle traverse every road exactly once? If so, which type?
1

List the degrees and identify odd ones

4 (even), 2 (even), 4 (even), 3 (odd), 3 (odd), 2 (even)

2

Count odd-degree vertices

There are 2 odd-degree vertices (the two with degree 3).

3

Apply the rule

2 odd-degree vertices β†’ Euler path exists. The vehicle can traverse every road once, but it will start and end at different intersections. It must begin (or end) at one of the two degree-3 intersections.

2 odd-degree vertices β†’ Euler path βœ“ (start at a degree-3 intersection)
πŸ“
Example B Β· Euler's Formula
A planar network diagram has 9 vertices and 13 edges. How many regions (faces) does it divide the page into?
1

Write the formula and substitute

v βˆ’ e + f = 2
9 βˆ’ 13 + f = 2

2

Solve for f

f = 2 βˆ’ 9 + 13 = 6

f = 6 faces (including the outer region)
Practice, tap to reveal answers
1
A graph has vertex degrees: 4, 3, 2, 3, 2. Is an Euler circuit, Euler path, or neither possible?
Tap to reveal β–Ύ
Odd-degree vertices: 3 (odd), 3 (odd) β†’ 2 odd-degree vertices
Result: Euler path (not a circuit, will start and end at different vertices)
Must start at one of the degree-3 vertices.
2
A graph has vertex degrees: 2, 4, 4, 2. Is an Euler circuit, Euler path, or neither possible?
Tap to reveal β–Ύ
All degrees are even: 2, 4, 4, 2 β†’ 0 odd-degree vertices
Result: Euler circuit, can start and end at the same vertex, tracing every edge once.
3
A connected planar graph has 5 vertices and 7 edges. How many faces does it have?
Tap to reveal β–Ύ
v βˆ’ e + f = 2
5 βˆ’ 7 + f = 2
f = 2 + 7 βˆ’ 5 = 4 faces
4
A graph has 4 vertices all with degree 3. Is it traversable? Explain.
Tap to reveal β–Ύ
All 4 vertices have degree 3 (odd) β†’ 4 odd-degree vertices
Result: Not traversable, with 4 or more odd-degree vertices, no Euler path or circuit is possible.
5
A planar map has 6 vertices and 9 edges. How many faces (regions) does it have?
Tap to reveal β–Ύ
v βˆ’ e + f = 2
6 βˆ’ 9 + f = 2
f = 2 + 9 βˆ’ 6 = 5 faces
Ready to practise?
πŸ™οΈ
Euler's District, Escape Room
The city's inspection robots are waiting for route clearance. Verify odd-degree counts, check traversability, and solve the planar graph formulas to deploy them.
Play β†’