IB Maths AI 3.13 Notes

Eulerian trails & circuits

In this section, we study important graph algorithms and optimisation problems. These ideas help us decide whether certain routes exist and how to find efficient networks or journeys. The main topics are Eulerian trails and circuits, Hamiltonian paths and cycles, minimum spanning trees, the Chinese postman problem, and the travelling salesman problem.

An Eulerian trail is a walk that uses every edge exactly once. An Eulerian circuit is an Eulerian trail that starts and ends at the same vertex.

These ideas depend on the degrees of the vertices.

• For a connected graph, an Eulerian circuit exists if every vertex has even degree.
• For a connected graph, an Eulerian trail exists if exactly $2$ vertices have odd degree. In that case, the trail starts at one odd vertex and ends at the other.
• If there are more than $2$ odd vertices, then neither an Eulerian trail nor an Eulerian circuit exists.

These conditions are useful because they let us decide quickly whether a graph can be traversed without repeating edges.

Suppose a connected graph has vertex degrees $2$, $4$, $4$, and $2$. Determine if an Eulerian circuit or trail exists.

Since all the degrees are even, an Eulerian circuit exists.

Now suppose a connected graph has vertex degrees $3$, $3$, $2$, and $4$. Determine if an Eulerian circuit or trail exists.

Exactly $2$ vertices have odd degree, so an Eulerian trail exists, but not an Eulerian circuit.