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. deg⁡(I)=5\deg(I) = 5 and deg⁡(N)=deg⁡(S)=deg⁡(E)=3\deg(N) = \deg(S) = \deg(E) = 3 — 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?

Choose one answer
Interactive

Trace every edge once

Vertices CC and FF have odd degree. Start at CC and try to use every edge exactly once. Then try starting at AA — where do you get stuck?

Worked example

Eulerian, semi-Eulerian or neither?

  • Simple familiar

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.

5 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Check that the graph is connected.

  2. Count the odd vertices: none means Eulerian; exactly two means semi-Eulerian, with the trail running between them; more than two means neither.

  3. Trace the trail edge by edge, ticking each one off.

Watch out for

  • Starting the trail at AA, BB, DD or EE. 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.

Select all that apply.

Worked example

Planning a street sweeper's route

  • Complex unfamiliar

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.

6 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Find the vertices of odd degree.

  2. With two odd vertices, repeat the shortest path between them.

  3. Total distance = all the edges + the repeated path.

Watch out for

  • Repeating BEBE and EFEF (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, BB and EE, 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.

Lesson 7 of 80% read

Save your progress with a free account