Lesson 7 of 8 · 18 min
Eulerian trails and circuits
Use the degrees of the vertices to decide whether a graph is Eulerian, semi-Eulerian or neither, find Eulerian trails and circuits, and solve route problems that must cover every edge.
What you will be able to do
- Define Eulerian trail, Eulerian circuit, Eulerian graph and semi-Eulerian graph.
- State and apply the conditions for an Eulerian circuit or an open Eulerian trail to exist.
- Find an Eulerian trail or circuit, starting at the right vertex.
- Solve practical problems, such as street sweeping and track inspection, that must cover every edge.
A street sweeper, a postie and a ranger inspecting walking tracks all share a goal: travel along every edge of a network, ideally without doubling back.
Sometimes that is possible and sometimes it is not — and you can tell which just by counting.
History
The bridges of Königsberg
In the 1700s the city of Königsberg (now Kaliningrad, Russia) had seven bridges joining the two banks of its river and two islands. People wondered whether they could stroll across every bridge exactly once. In 1736 Leonhard Euler proved it was impossible, using nothing but the number of bridges at each piece of land. His argument is the start of graph theory.
Königsberg as a graph: each piece of land is a vertex and each bridge is an edge. and — every vertex is odd.
Definition
Eulerian trails, circuits and graphs
- An Eulerian trail is a trail that uses every edge of the graph exactly once. It may be open or closed.
- An Eulerian circuit is a closed Eulerian trail: it uses every edge exactly once and finishes where it started.
- A connected graph with an Eulerian circuit is an Eulerian graph.
- A connected graph with an open Eulerian trail but no Eulerian circuit is a semi-Eulerian graph.
Key idea
The conditions
For a connected graph, count the vertices of odd degree:
- No odd vertices — the graph is Eulerian. It has an Eulerian circuit, which can start at any vertex.
- Exactly two odd vertices — the graph is semi-Eulerian. It has an open Eulerian trail, which must start at one odd vertex and finish at the other.
- More than two odd vertices — neither. No route can use every edge exactly once.
A graph never has exactly one odd vertex: the number of odd vertices is always even.
Why the degrees decide it
Follow a trail through a vertex in the middle of the route: you arrive along one edge and leave along another. Each visit uses 2 edges at that vertex, so every vertex passed through needs an even degree.
Only the start and the finish can be different. The start has one extra edge leaving and the finish one extra edge arriving. If the trail is closed, start and finish are the same vertex and those two extras pair up, so every degree is even. If the trail is open, the start and the finish are the only odd vertices.
In Königsberg all four pieces of land have odd degree, so no stroll crosses every bridge exactly once.
A connected graph has six vertices with degrees 2, 4, 3, 2, 3 and 4. Which statement is true?
Vertices and have odd degree. Start at and try to use every edge exactly once. Then try starting at — where do you get stuck?
Worked example
Eulerian, semi-Eulerian or neither?
For the graph shown:
(a) decide whether it is Eulerian, semi-Eulerian or neither, and justify your decision
(b) write down an Eulerian trail if one exists.
Step 1: Check that the graph is connected
Every vertex can be reached from every other vertex, so the graph is connected.
Step 2: Find every degree
, , , , ,
Step 3: Count the odd vertices
Exactly two vertices, and , have odd degree.
Step 4: Apply the conditions
A connected graph with exactly two odd vertices is semi-Eulerian. It has an open Eulerian trail, which must start at one odd vertex and finish at the other. It has no Eulerian circuit, because that needs every degree to be even.
Step 5: Trace the trail from C, ticking off edges
–––––––––. It uses 9 edges, each once, and the graph has 9 edges. ✓
At each vertex, avoid an edge that would leave other unused edges cut off from you. Ticking edges off as you go makes the final check easy.
Try it yourself first, then check the working one step at a time.
Answer
(a) Semi-Eulerian: the graph is connected and exactly two vertices, and , have odd degree. (b) For example –––––––––. Every Eulerian trail runs from to or from to .
Method
Check that the graph is connected.
Count the odd vertices: none means Eulerian; exactly two means semi-Eulerian, with the trail running between them; more than two means neither.
Trace the trail edge by edge, ticking each one off.
Watch out for
Starting the trail at , , or . You will get stuck before every edge is used.
A ranger wants to walk along every track in the national park exactly once. The walk does not have to finish where it starts. At which two places must the walk start and finish? Select both.
Worked example
Planning a street sweeper's route
A council street sweeper must travel along every street shown at least once, starting and finishing at the depot. Street lengths are in metres.
(a) Explain why the sweeper cannot travel every street exactly once and return to the depot.
(b) Find the shortest total distance the sweeper must travel, and state which streets it should travel twice.
Step 1: Recognise what is being asked
Travelling every street exactly once and returning to the start is an Eulerian circuit. That needs a connected graph in which every vertex has even degree.
Step 2: Check the degrees
Depot 2, 4, 3, 2, 4, 3. Vertices and have odd degree, so there is no Eulerian circuit: the sweeper must travel some streets twice.
Step 3: Decide which streets to repeat
Repeating the streets along a route from to adds 1 to the degrees of and , making them even, and 2 to each vertex in between, keeping them even. So the sweeper should repeat the shortest path from to .
A route passing through a vertex arrives on one edge and leaves on another, adding 2 there. Only the two ends of the repeated route change from odd to even.
Step 4: Find the shortest path from B to F
- ––: m
- ––: m
- Longer routes, such as ––– at 950 m, are not needed.
The shortest is ––, 600 m.
Step 5: Total the distance
All the streets: m. Adding the repeated 600 m gives m.
Step 6: Give a route that achieves it
For example: Depot–––––––––––Depot. It uses and twice and every other street once, a total of 3650 m. ✓
Try it yourself first, then check the working one step at a time.
Answer
(a) and have odd degree, so the network has no Eulerian circuit. (b) 3650 m, travelling streets and twice — the shortest path from to .
Method
Find the vertices of odd degree.
With two odd vertices, repeat the shortest path between them.
Total distance = all the edges + the repeated path.
Watch out for
Repeating and (650 m) gives a valid route, but not the shortest.
Answering 3050 m, which ignores the doubling back.
Tip
Fixing the odd vertices
Adding an edge between two odd vertices makes both of them even. So a semi-Eulerian graph becomes Eulerian if you add an edge joining its two odd vertices — or, in practice, if you travel the shortest path between them a second time, as the street sweeper did.
A connected graph has exactly 4 vertices of odd degree. What is the least number of edges that must be added to make it Eulerian?
Common mistake
Three common errors
- Starting at the wrong vertex. In a semi-Eulerian graph, start at an odd vertex or you will get stuck.
- Forgetting connectivity. A graph in two pieces has no Eulerian trail, even if every degree is even.
- Confusing Eulerian with Hamiltonian. Eulerian is about every edge; Hamiltonian (the next lesson) is about every vertex.
Exam tip
Justify with degrees, naming the odd vertices: "The graph is semi-Eulerian because exactly two vertices, and , have odd degree and the rest are even." QCAA writes "open Eulerian trail" and "closed Eulerian trail" — the closed one is the Eulerian circuit. The conditions are not in the formula book, so learn them.
Summary
An Eulerian trail uses every edge exactly once; an Eulerian circuit does so and returns to its start.
Connected with 0 odd vertices: Eulerian — an Eulerian circuit exists, starting anywhere.
Connected with 2 odd vertices: semi-Eulerian — an open Eulerian trail runs from one odd vertex to the other.
More than 2 odd vertices means neither.
To cover every edge and return to the start in a semi-Eulerian network, repeat the shortest path between the two odd vertices.
Finished the lesson?
Try the 3 quick checks above and the lesson completes itself, or mark it complete now.