Euler Trails and Circuits
Amazingly, it is possible to determine if an undirected network will have an Euler trail or circuit without having to actually find it! Here’s how to tell:
- If a network has exactly two vertices of odd degree, then the network has an Euler trail (and so it is traversable). These two vertices will be the start and the end of the trail.
- If a network has no vertices of odd degree, then the network has an Euler circuit (and so it is an Euler network).
Still, it can take some practice to get proficient at being able to find Euler trails or Euler circuits - knowing they exist is not the same as seeing one in front of you! To help us we are going to us a procedure called Fleury's Algorithm (pronounced FLOO-ree). It was first published by a French mathematician named M. Fleury in 1883 - the 'M.' likely stands for 'Monsieur', so their first name was lost to history.
- Make sure the graph has either $0$0 or $2$2 vertices with odd degree.
- If there are no edges with odd degree, start anywhere. If there are $2$2, pick one of them to start from.
- Follow edges one at a time, eliminating the edges you pick from the network as you go.
- If you have a choice between a bridge and a non-bridge from the remaining edges, always choose the non-bridge.
- Stop when you run out of edges.
Seems simple enough - let’s try it out:
Fleury’s algorithm in action.
This algorithm will find the Euler trail (or circuit) every time. It helps best in the tricky situations where you don’t know which edge to pick - if you choose a bridge before a non-bridge you won’t be able to get back.
For directed networks, we can still have Euler trails and Euler circuits, but there’s no easy way to find them like there is for undirected networks, you just have to give it a go. Let’s return once again to the garbage collection example from earlier:
Can you find the Euler circuit now you know Fleury's algorithm? Since you’re looking for a circuit, it doesn’t matter which vertex you start from. Use the Hamiltonian cycle we found earlier to help you.
One final note before we finish this section: a network can be a traversable/Euler network, a traceable/Hamiltonian network, both, or neither, as these examples demonstrate:
The first is an Euler and a Hamiltonian network, the second is only a Hamiltonian network, the third is only an Euler network, and the fourth is neither.
In summary,
- A network is traceable if there is a path that visits every vertex, and Hamiltonian if you can do it with a circuit (closed path).
- A network is traversable if there is a trail that uses every edge, and Euler if you can do it with a cycle (closed trail).