Lesson 7: Eulerian trails and circuits

Eulerian, semi-Eulerian or neither?

SkillEulerian trails and circuits

Worked example

  • Simple familiar

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.

1 of 5 steps
  1. Step 1: Check that the graph is connected

    Every vertex can be reached from every other vertex, so the graph is connected.

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. Check that the graph is connected.

  2. Count the odd vertices: none means Eulerian; exactly two means semi-Eulerian, with the trail running between them; more than two means neither.

  3. Trace the trail edge by edge, ticking each one off.

Watch out for

  • Starting the trail at AA, BB, DD or EE. You will get stuck before every edge is used.

Save your progress with a free account