Lesson 8 ~40 min Introduction to Networks · Path +90 XP

Eulerian Trails and Circuits

An Eulerian trail is the answer to a question people actually ask: can this whole system be covered without doing anything twice? It is a trail rather than a path, and that distinction is what makes it possible at all.

Today's hook: A snow plough must clear every road in a suburb. Doing a road twice wastes fuel and time, so the ideal round covers each road exactly once. Whether such a round exists, and whether it can end back at the depot, are two different questions.

0/5QUESTS

Think First

warm-up

Look at the numbered diagram above. Follow the edges in order $1$ to $6$. Did you use every edge? Did you use any edge twice? Where did you finish?

Record your answer in your workbook.

The Big Idea

+5 XP to read

An Eulerian trail is a trail that uses every edge of the graph exactly once. An Eulerian circuit is an Eulerian trail that also finishes where it started.

$$\text{Eulerian trail} + \text{closed} = \text{Eulerian circuit}$$

The word every does the work. A trail uses no edge twice, which is easy; an Eulerian trail must also leave none behind, and that is what makes it rare.

$\text{every edge, exactly once}$

Edges, not vertices

Eulerian journeys cover every edge. Covering every vertex is a different problem with a different name.

Vertices may be revisited

It is a trail, not a path, so passing through the same junction several times is expected.

Count before you claim

An Eulerian trail on a graph with $e$ edges has length exactly $e$. Check that before writing it down.

What You'll Master

objectives

Know

that an Eulerian trail is a trail that includes every edge of the graph exactly once
that an Eulerian circuit is an Eulerian trail that ends at its starting vertex
that an Eulerian trail on a graph with $e$ edges has length exactly $e$

Understand

why an Eulerian journey must be a trail rather than a path
why a graph must be connected for an Eulerian trail to exist
why some graphs admit an Eulerian trail but no Eulerian circuit

Can Do

verify that a proposed journey is an Eulerian trail or circuit
find an Eulerian trail or circuit in a small graph by inspection
explain why a particular proposed journey fails to be Eulerian

Words You Need

vocabulary

Eulerian trailA trail that uses every edge of the graph exactly once.

Eulerian circuitAn Eulerian trail that finishes at the vertex it started from.

TraverseTo travel along an edge. An Eulerian trail traverses every edge once.

Semi-EulerianHaving an Eulerian trail but no Eulerian circuit.

Eulerian graphA graph that has an Eulerian circuit.

The Definition

+5 XP to read

An Eulerian trail is a trail that includes every edge of the graph exactly once.

Two conditions are packed into that sentence. Because it is a trail, no edge may be used twice. Because it is Eulerian, no edge may be left out. Together those force each edge to be used exactly once, which is much more demanding than either alone.

An Eulerian circuit is an Eulerian trail that also finishes at the vertex it started from.

These are journeys about edges. There is no requirement to visit every vertex, although in a connected graph that happens automatically, since every vertex has an edge and every edge is used.

A graph with an Eulerian circuit is called an Eulerian graph. One with an Eulerian trail but no circuit is sometimes called semi-Eulerian.

Why It Must Be a Trail

+5 XP to read

Lesson 7 flagged this and it is worth doing properly.

Consider a vertex of degree $4$. Four edges meet there, and all four must be used. Each time the journey passes through the vertex it arrives on one edge and leaves on another, using two of them.

So covering all four requires passing through that vertex at least twice, and the journey must therefore revisit it.

A path forbids revisiting any vertex, so a path could never cover all four edges. The vertex restriction has to be dropped, and dropping it is exactly what turns a path into a trail.

In general a vertex of degree $d$ needs to be passed through about $\dfrac{d}{2}$ times, so the higher the degrees, the more revisiting is required, and the more essential it is that the journey is a trail.

Connectedness Is Required

+5 XP to read

An Eulerian trail must use every edge in the graph. If the graph has two components, the trail would have to include edges from both.

But a journey travels along edges, and no edge joins one component to another. Once the journey is inside one component it can never leave it.

So a disconnected graph with edges in more than one component has no Eulerian trail, and the question is settled before any attempt is made.

Check connectedness first, always. It costs one exploration from any vertex and it can save a great deal of fruitless searching.

An isolated vertex with no edges is harmless, since there are no edges there to be covered. It is edges in a second component that make an Eulerian trail impossible.

Finding One by Hand

+5 XP to read

For a small graph, trial and error works, but a little strategy makes it far quicker.

Count the edges first. A graph with $e$ edges has an Eulerian trail of length exactly $e$, so you know in advance how many steps to write down and can check the count at the end.

Cross off edges as you use them. Working from a list rather than a picture makes it much harder to use one twice by accident.

Do not burn your bridges. If using an edge would cut off part of the graph you still need to reach, save that edge for later. This is the one genuine piece of technique, and it is what turns guesswork into a method.

If you get stuck with edges remaining, that is not a proof that none exists. It may just be a bad first choice, and the next lesson supplies a test that settles the question without any searching at all.

Trail Without Circuit

+5 XP to read

Some graphs have an Eulerian trail but no Eulerian circuit, and the distinction is not a technicality.

Take a graph shaped like a triangle with an extra edge hanging off one corner. Every edge can be covered in one trail: walk round the triangle and then out along the tail. But that trail ends at the tip of the tail, not where it began.

No rearrangement helps. The tip of the tail has only one edge, so a journey either starts there or ends there, and either way it cannot both start and end at the same vertex while covering the tail edge once.

So "can every edge be covered once?" and "can that be done as a round trip?" are genuinely different questions.

For the snow plough this is the difference between a shift that ends at the depot and one that ends across the suburb, which is a practical difference worth knowing about before the shift starts.

Watch Me Solve It · 3 examples

Watch Me Solve It · Verifying an Eulerian circuit

+15 XP per step

PROBLEM

The graph has vertices $A$ to $E$ and edges $AB$, $BC$, $CD$, $DE$, $EA$, $AD$. Show that $A \to B \to C \to D \to E \to A \to D$ is not an Eulerian circuit, and find one that is.

1

Check the proposed journey against the definition

$\text{edges used: } AB, BC, CD, DE, EA, AD$

All six edges are used and none is repeated, so it is an Eulerian trail. But it finishes at $D$, not at $A$, so it is not a circuit.
2

Count what an Eulerian circuit would need

$e = 6$

Any Eulerian journey here has length $6$, using six edges and listing seven vertices.
3

Show that closing it fails

$A \to B \to C \to D \to A \to E$

This uses $AB$, $BC$, $CD$, $DA$, $AE$, which is five edges, and leaves $DE$ unused with the journey stranded at $E$.
4

State the conclusion

The proposed journey is an Eulerian trail but not a circuit, and the attempt to close it fails. Lesson 9 explains why: $A$ and $D$ have odd degree, which permits a trail between them but forbids a circuit.

AnswerIt is an Eulerian trail but not a circuit, since it ends at $D$ rather than $A$

Watch Me Solve It · Finding an Eulerian circuit

+15 XP per step

PROBLEM

The graph has vertices $P$, $Q$, $R$, $S$ and edges $PQ$, $QR$, $RS$, $SP$, $PR$, and a second edge $PR$. Find an Eulerian circuit and verify it.

1

Count the edges

$e = 6$

Six edges, counting the two $PR$ edges separately. Any Eulerian circuit has length $6$.
2

Write a candidate

$P \to Q \to R \to P \to R \to S \to P$

The two visits to $R$ use the two different $PR$ edges, one in each direction.
3

Check every edge is used once

$PQ, \ QR, \ RP_1, \ PR_2, \ RS, \ SP$

Six edges listed, all different, and they are exactly the six edges of the graph. So it is an Eulerian trail.
4

Check it is closed

It starts at $P$ and finishes at $P$, so it is an Eulerian circuit. The vertex $P$ appears three times and $R$ twice, which is what degree $4$ requires: $R$ is passed through twice, using two edges each time, while $P$'s three appearances are the start, one pass through, and the finish.

Answer$P \to Q \to R \to P \to R \to S \to P$, using all six edges once and returning to $P$

Watch Me Solve It · Trail but no circuit

+15 XP per step

PROBLEM

A graph is a triangle $XYZ$ with an extra vertex $W$ joined only to $X$. Find an Eulerian trail, and explain why no Eulerian circuit exists.

1

List the edges

$XY, \ YZ, \ ZX, \ XW$

Four edges, so an Eulerian journey has length $4$.
2

Find a trail

$W \to X \to Y \to Z \to X$

Uses $WX$, $XY$, $YZ$, $ZX$, all four, none repeated. It is an Eulerian trail, starting at $W$ and finishing at $X$.
3

Explain why it cannot be closed

The vertex $W$ has degree $1$, so it has exactly one edge. A journey passing through $W$ would need to arrive on one edge and leave on another, and there is no second edge to leave on.
4

Complete the argument

So $W$ can only be an endpoint of the journey. An Eulerian circuit has no endpoints other than its start, which it also finishes at, and $W$ cannot serve as both while its single edge is used once. Hence no Eulerian circuit exists.

Answer$W \to X \to Y \to Z \to X$ is an Eulerian trail; no circuit exists because $W$ has degree $1$

Brain Trainer · 5 problems

Brain Trainer · Every edge, once

5 problems

Five items on Eulerian journeys. Count the edges before checking any proposed route.

1 What does an Eulerian trail use exactly once?

The requirement is about edges, not vertices.Every edge
2 A graph has $9$ edges. How long is any Eulerian trail on it?

Each edge is used exactly once.$9$
3 What extra condition turns an Eulerian trail into an Eulerian circuit?

The difference is about where it finishes.It ends where it started
4 Can a disconnected graph with edges in two components have an Eulerian trail?

A journey cannot cross between components.No
5 Why must an Eulerian journey be a trail rather than a path?

A vertex of degree $4$ needs two visits to cover its edges.It must revisit vertices

Complete in your workbook.

Multiple Choice · 5 questions

MC1

The definition

+10 XP

An Eulerian trail is a trail that:

MC2

Trail against circuit

+10 XP

A journey uses every edge of a connected graph exactly once and finishes at a different vertex from the one it started at. It is:

MC3

The length

+10 XP

A connected graph has $12$ edges and $7$ vertices. Any Eulerian trail on it has length:

MC4

Ruling it out quickly

+10 XP

A graph has two components, each containing several edges. The number of Eulerian trails it has is:

MC5

Why not a path

+10 XP

A vertex has degree $6$. Any Eulerian journey on that graph must pass through the vertex at least:

Short Answer · 3 questions

Verify a proposed journey

+15 XP

SHORT ANSWER

A graph has vertices $A$, $B$, $C$, $D$ and edges $AB$, $BC$, $CD$, $DA$, $AC$, $BD$. A student proposes the journey $A \to B \to C \to D \to A \to C$. Determine whether it is an Eulerian trail, an Eulerian circuit, or neither, giving full reasons.

Write your working in your book.

Find one and explain the limit

+15 XP

SHORT ANSWER

A graph has vertices $P$, $Q$, $R$, $S$, $T$ and edges $PQ$, $QR$, $RS$, $SP$, $PR$, $QT$, $TR$. Find an Eulerian trail if one exists, state where it starts and finishes, and explain why it cannot be closed.

Write your working in your book.

Model a plough round

+15 XP

SHORT ANSWER

A suburb's roads form a connected network with $14$ road sections. A snow plough must clear every section once. Explain in network terms what the plough is looking for, state how long the round will be, and explain what difference it makes to the operator whether an Eulerian circuit exists rather than only an Eulerian trail.

Write your working in your book.

Stretch Challenge · Why the odd vertices decide everything

+25 XP

CHALLENGE

Suppose a graph has an Eulerian circuit. Explain why every vertex must have even degree. Then suppose it has an Eulerian trail that is not closed, and explain why exactly two vertices have odd degree. Say what these two results together let you conclude before attempting any search.

The circuit case. Take any vertex $V$ and follow the circuit. Every time the journey passes through $V$ it arrives along one edge and departs along another, using exactly two of $V$'s edges.

Because the circuit is closed, this is also true at the starting vertex: the journey departs along one edge at the beginning and arrives along another at the end, and those two pair up just like any other pass through.

The circuit uses every edge at $V$ exactly once, and it uses them in pairs, so the number of edges at $V$ is a multiple of $2$. Therefore $\deg(V)$ is even. Since $V$ was any vertex, every degree is even.

The open trail case. The same pairing argument applies at every vertex the journey merely passes through, so all of those have even degree.

The two exceptions are the start and the finish. At the start the journey departs without having arrived, so one edge there is unpaired, and the degree is an even number plus $1$, which is odd. The same happens at the finish, where it arrives without departing.

Since the trail is not closed, the start and finish are different vertices, so exactly two vertices have odd degree.

What this lets you conclude. Count the odd-degree vertices before searching. If there are more than two, no Eulerian trail exists and no amount of searching will produce one. If there is exactly one, that is impossible anyway, since Lesson 2 showed the number of odd vertices is always even.

So the only counts that permit an Eulerian journey are zero and two, and they correspond exactly to the circuit case and the open trail case respectively.

One caution about what has been proved. These arguments show the degree conditions are necessary: if an Eulerian journey exists, the degrees look like this. They do not by themselves show the conditions are enough. That they are also sufficient for a connected graph is a genuine theorem, and it is what Lesson 9 states and Lesson 10 applies.

Quick Review

recap

Every edge, exactly once

An Eulerian trail is a trail using every edge of the graph once. An Eulerian circuit is one that also returns to its starting vertex.

A trail, never a path

A vertex of degree $d$ must be passed through about $\tfrac{d}{2}$ times to cover its edges, so revisiting vertices is required rather than merely permitted.

Connectedness is required

No journey crosses between components, so a graph with edges in two components has no Eulerian trail. Check this first.

Length equals the edge count

A graph with $e$ edges has Eulerian journeys of length exactly $e$, listing $e + 1$ vertices. Checking the length rules out a wrong answer in one line.

Your Badges

0 of 6

First Steps

3-Day Streak

3 in a Row

Lesson Ace

Stretch Seeker

Daily Warrior

Mark lesson as complete

Tick when you've finished Learn, Practice and the Stretch. Earns +90 XP and +25 coins.

Introduction to Networks (Path) index · Maths subject page