Paths, Cycles and Euler Trails

In the Bridges of Königsberg problem, we were trying to find a route that used every edge exactly once.

Graph theory has names for different kinds of routes through a graph.

Routes through a graph

Consider the following graph:

Definition

Path

💡

Learning tip Try making up your own example and a non-example. A route may look almost like a path, but fail because it visits one vertex twice.

A path follows edges of a graph without visiting the same vertex twice.

Example: A → B → C → D

Definition

Cycle

A cycle returns to its starting vertex, without repeating any other vertex.

Example: A → B → C → A

Definition

Trail

A trail follows edges without using the same edge twice. It may visit the same vertex more than once.

Example: C → A → B → C → D → E

Definition

Euler trail

An Euler trail is a trail that uses every edge of the graph exactly once. It does not have to finish where it started.

Example: C → A → B → C → D → E → F → D

Definition

Euler circuit

An Euler circuit is an Euler trail that finishes at the same vertex where it started.

The graph above has an Euler trail, but not an Euler circuit.

Example on a different graph: A → B → C → D → A

What type of route is it?

Here are three routes on the same graph. Look at the highlighted edges and decide what kind of route each one is.

Example

Route 1

A → B → C → D

Reveal answer

This is a path.

No vertex is repeated. It is also a trail because no edge is repeated.

It is not an Euler trail because it does not use every edge of the graph.

Example

Route 2

A → B → C → D → E → A

Reveal answer

This is a cycle.

It starts and finishes at the same vertex, and no other vertex is repeated.

It is also a trail, because no edge is repeated, but it is not an Euler circuit because it does not use every edge of the graph.

Example

Route 3

A → B → C → D → E → A → C

Reveal answer

This is an Euler trail.

Every edge of the graph is used exactly once.

It is a trail because no edge is repeated, but it is not a path because the vertex A is visited more than once.

It is also not an Euler circuit, because it finishes at C rather than returning to the starting vertex A.

Interactive challenge

Build a route

Click any vertex to choose where to start. Then click a connected vertex to travel along an edge. Your route will be highlighted as you go.

💡

Learning tip If a route gets stuck, don’t immediately start again. Look at where it failed. Which unused edges are left, and what made them impossible to reach? A failed attempt can tell you what to try differently next time.

Make a path

Travel along at least 4 edges without visiting any vertex twice.

Your route

Choose a starting vertex

Edges travelled

0 / 15

Tip: if an edge turns pink, you have travelled along that edge more than once.

The degree rule

In the previous lesson, we discovered that odd and even degrees tell us whether an Euler trail is possible.

Important rule

When does a graph have an Euler trail?

For a connected graph:

Zero odd-degree vertices → the graph has an Euler circuit.
Two odd-degree vertices → the graph has an Euler trail, but not an Euler circuit.
More than two odd-degree vertices → the graph has no Euler trail.

Practice puzzles

Puzzle 1 – Use the rule

A connected graph has vertex degrees:

4, 2, 2, 2, 2

Without drawing the graph, decide:

Does it have an Euler trail?
Does it have an Euler circuit?

Hint: How many vertices have odd degree?

Reveal answer

All five degrees are even, so there are 0 odd-degree vertices.

Therefore the graph has an Euler circuit — and hence also an Euler trail.

Puzzle 2 – Use the rule

A connected graph has vertex degrees:

4, 3, 2, 2, 1

Without drawing the graph, decide:

Does it have an Euler trail?
Does it have an Euler circuit?
Where must the trail start and finish?

Reveal answer

There are exactly two odd-degree vertices: 3 and 1.

So the graph has an Euler trail, but not an Euler circuit.

The trail must start at one odd-degree vertex and finish at the other.

Puzzle 3 – What happens with four odd vertices?

A connected graph has degrees:

3, 3, 2, 2, 1 and 1

Without drawing the graph, decide:

Does it have an Euler trail?
Does it have an Euler circuit?
What feature of the degree list tells you immediately?

Reveal answer

There are four odd-degree vertices: 3,3,1 and 1.

An Euler trail is possible only when there are zero or two odd-degree vertices.

So the graph has no Euler trail and therefore no Euler circuit.

You do not need to know what the graph looks like — counting the odd-degree vertices is enough.

Challenge

Repair the graph

💡

Learning tip Change just one thing at a time, then check what happened to the degrees of the vertices. Can you predict the effect of adding an edge before you try it?

This graph has four odd-degree vertices, so it does not have an Euler trail.

Add exactly one new edge so that an Euler trail becomes possible.

Click one vertex, then another vertex to join them.

Choose two vertices.

In the next lesson, we’ll use these ideas on a classic type of puzzle:

Can you draw a picture without lifting your pencil or drawing any line twice?

Keep learning

Come back to it later

When you learn something new, it is important to come back to it later. Revisiting an idea after some time has passed helps you discover what you remember, what needs another look, and often makes the idea clearer the second time around. Our handouts are a perfect excuse to do exactly that.

📘

Printable Graphs course

Prefer paper, a tablet, or studying offline? Open the printable version of the whole Graphs course, including this lesson.

Open printable PDF →

✏️