Eulerian Trails & Circuits
What are Eulerian trails and circuits?
- A trail is a walk in which no edge is repeated
- An Eulerian trail is a trail that visits each edge in a graph exactly once
- A circuit is a trail that begins and ends at the same vertex
- An Eulerian circuit is a trail that visits each edge in a graph exactly once and begins and ends at the same vertex
- A graph which contains an Eulerian circuit is called an Eulerian graph
- In an Eulerian graph the degree of each vertex is even
- A semi-Eulerian graph contains an Eulerian trail but not an Eulerian circuit
- In a semi-Eulerian graph exactly one pair of vertices have an odd degree
- These are the start and finish points of any Eulerian trail
- An adjacency matrix can be used to determine if a graph is Eulerian or semi-Eulerian as the degree of each vertex can be found by inspecting the sum of the entries in the rows (out-degree) or columns (in-degree)
Examiner Tip
- If you can draw a graph without taking your pen off the paper and without going over any edge more than once then you have an Eulerian or semi-Eulerian graph!
Worked example
Let G be the graph shown below.