6.3: Euler Circuits
- Page ID
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.
A path that travels through every edge of a connected graph once and only once and starts and ends at different vertices
One Euler path for the above graph is F, A, B, C, F, E, C, D, E as shown below.
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.
An Euler path that starts and ends at the same vertex
One Euler circuit for the above graph is E, A, B, F, E, F, D, C, E as shown below.
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.
If a graph is connected and every vertex has an even degree, then it has at least one Euler circuit (usually more).
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.
Therefore, the number of vertices of odd degree must be even.
- Be sure that every vertex in the network has even degree.
- Begin the Euler circuit at any vertex in the network.
- 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.
- 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.
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.
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.