6.3: Euler Circuits

Leonhard Euler first discussed and used Euler paths and circuits in 1736. Rather than finding a minimum spanning tree that visits every vertex of a graph, an Euler path or circuit can be used to find a way to visit every edge of a graph once and only once. This would be useful for checking parking meters along the streets of a city, patrolling the streets of a city, or delivering mail.

Definition: Euler Path

A path that travels through every edge of a connected graph once and only once and starts and ends at different vertices

Example \(\PageIndex{1}\): Euler Path

Figure \(\PageIndex{1}\): Euler Path Example

One Euler path for the above graph is F, A, B, C, F, E, C, D, E as shown below.

Figure \(\PageIndex{2}\): Euler Path

This Euler path travels every edge once and only once and starts and ends at different vertices. This graph cannot have an Euler circuit since no Euler path can start and end at the same vertex without crossing over at least one edge more than once.

Definition: Euler Circuit

An Euler path that starts and ends at the same vertex

Example \(\PageIndex{2}\): Euler Circuit

Figure \(\PageIndex{3}\): Euler Circuit Example

One Euler circuit for the above graph is E, A, B, F, E, F, D, C, E as shown below.

Figure \(\PageIndex{4}\): Euler Circuit

This Euler path travels every edge once and only once and starts and ends at the same vertex. Therefore, it is also an Euler circuit.

Euler’s Theorem \(\PageIndex{1}\): If a graph has any vertices of odd degree, then it cannot have an Euler circuit.

If a graph is connected and every vertex has an even degree, then it has at least one Euler circuit (usually more).

Euler’s Theorem \(\PageIndex{2}\): If a graph has more than two vertices of odd degree, then it cannot have an Euler path.

If a graph is connected and has exactly two vertices of odd degree, then it has at least one Euler path (usually more). Any such path must start at one of the odd-degree vertices and end at the other one.

Euler’s Theorem \(\PageIndex{3}\): The sum of the degrees of all the vertices of a graph equals twice the number of edges (and therefore must be an even number).

Therefore, the number of vertices of odd degree must be even.

Finding Euler Circuits

1. Be sure that every vertex in the network has even degree.
2. Begin the Euler circuit at any vertex in the network.
3. As you choose edges, never use an edge that is the only connection to a part of the network that you have not already visited.
4. Label the edges in the order that you travel them and continue this until you have travelled along every edge exactly once and you end up at the starting vertex.

Example \(\PageIndex{3}\): Finding an Euler Circuit

Figure \(\PageIndex{5}\): Graph for Finding an Euler Circuit

The graph shown above has an Euler circuit since each vertex in the entire graph is even degree. Thus, start at one even vertex, travel over each vertex once and only once, and end at the starting point. One example of an Euler circuit for this graph is A, E, A, B, C, B, E, C, D, E, F, D, F, A. This is a circuit that travels over every edge once and only once and starts and ends in the same place. There are other Euler circuits for this graph. This is just one example.

Figure \(\PageIndex{6}\): Euler Circuit

The degree of each vertex is labeled in red. The ordering of the edges of the circuit is labeled in blue and the direction of the circuit is shown with the blue arrows.