An Eulerian trail is a route through a graph that uses every edge exactly once. An Eulerian circuit also uses every edge exactly once, but finishes at the vertex where it started.
This is HL-only content in AHL 3.16: Tree and cycle algorithms. It can be tested in any Mathematics: Applications and Interpretation HL paper style, and every paper is GDC-active, although this test is normally completed by inspection.
How to Determine Whether One Exists
First, check that all vertices with at least one incident edge belong to one connected graph. Isolated vertices can be ignored because they are not involved in any edge.
Next, calculate the degree of each vertex, meaning the number of edges incident to it. A loop contributes two to the degree of its vertex.
| Number of odd-degree vertices | Conclusion |
|---|---|
| None | An Eulerian circuit exists; therefore, an Eulerian trail also exists. |
| Exactly two | An Eulerian trail exists, but no Eulerian circuit exists. The trail must start and finish at the two odd-degree vertices. |
| More than two | Neither an Eulerian trail nor an Eulerian circuit exists. |
The reason is that whenever a route enters an intermediate vertex along one edge, it must leave along another. These edges therefore occur in pairs, giving intermediate vertices even degree. In a non-closed trail, only the starting and finishing vertices can have unpaired edges.
For example, suppose a connected graph has vertex degrees . Exactly two vertices have odd degree, so an Eulerian trail exists between those two vertices, but an Eulerian circuit does not.
Exam Technique
State both required checks: connectedness and the number of odd-degree vertices. Do not merely write “two odd vertices”; identify them and state that they must be the endpoints.
A common misconception is confusing Eulerian routes with Hamiltonian routes. Eulerian trails use every edge exactly once, whereas Hamiltonian paths visit every vertex exactly once.
