Lesson 7: Eulerian trails and circuits
Eulerian, semi-Eulerian or neither?
SkillEulerian trails and circuits
Worked example
For the graph shown:
(a) decide whether it is Eulerian, semi-Eulerian or neither, and justify your decision
(b) write down an Eulerian trail if one exists.
Step 1: Check that the graph is connected
Every vertex can be reached from every other vertex, so the graph is connected.
Step 2: Find every degree
, , , , ,
Step 3: Count the odd vertices
Exactly two vertices, and , have odd degree.
Step 4: Apply the conditions
A connected graph with exactly two odd vertices is semi-Eulerian. It has an open Eulerian trail, which must start at one odd vertex and finish at the other. It has no Eulerian circuit, because that needs every degree to be even.
Step 5: Trace the trail from C, ticking off edges
–––––––––. It uses 9 edges, each once, and the graph has 9 edges. ✓
At each vertex, avoid an edge that would leave other unused edges cut off from you. Ticking edges off as you go makes the final check easy.
Answer
(a) Semi-Eulerian: the graph is connected and exactly two vertices, and , have odd degree. (b) For example –––––––––. Every Eulerian trail runs from to or from to .
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
Check that the graph is connected.
Count the odd vertices: none means Eulerian; exactly two means semi-Eulerian, with the trail running between them; more than two means neither.
Trace the trail edge by edge, ticking each one off.
Watch out for
Starting the trail at , , or . You will get stuck before every edge is used.