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

Trails, Paths, Circuits and Cycles

A walk allows every kind of repetition. Forbidding repeated edges gives one kind of journey, forbidding repeated vertices gives another, and asking whether the journey returns to its start doubles each of them.

Today's hook: Four words, all meaning "a way through the network", all different, and all appearing in the same exam question. The differences are small, precise, and entirely learnable in one diagram.

0/5QUESTS

Think First

warm-up

A postal worker must walk down every street exactly once. A tourist wants to see five landmarks without passing anything twice. Which of the two is allowed to visit the same corner more than once?

Record your answer in your workbook.

The Big Idea

+5 XP to read

Two questions classify every journey. Does it repeat an edge? Does it repeat a vertex? And a third doubles the answers: does it end where it started?

$$\text{trail} \to \text{circuit}, \qquad \text{path} \to \text{cycle}$$

The names follow one pattern. A trail repeats no edge; close it and it becomes a circuit. A path repeats no vertex; close it and it becomes a cycle. Learn the two open ones and the closed ones follow.

$\text{trail, path, circuit, cycle}$

Edges for trails, vertices for paths

Trail bans repeated edges. Path bans repeated vertices, which is the stronger restriction.

Every path is a trail

Using an edge twice means visiting its endpoints twice, so no repeated vertex means no repeated edge.

A cycle's start counts once

A cycle returns to its first vertex, and that single repetition is allowed by definition.

What You'll Master

objectives

Know

that a trail is a walk with no repeated edge, and a path is a walk with no repeated vertex
that a circuit is a closed trail and a cycle is a closed path
that in a cycle the starting vertex is the only one permitted to appear twice

Understand

why every path is automatically a trail, but not every trail is a path
why the two restrictions come from two different questions rather than being degrees of the same one
why a postal round and a sightseeing tour need different kinds of journey

Can Do

classify a given walk as a trail, a path, a circuit, a cycle, or none of these
find a trail, path, circuit or cycle of a given length in a graph
explain why a particular walk fails to be a path or a trail

Words You Need

vocabulary

TrailA walk with no repeated edge. Vertices may be revisited.

PathA walk with no repeated vertex, and therefore no repeated edge either.

CircuitA closed trail: it uses no edge twice and finishes where it started.

CycleA closed path: it repeats no vertex except the starting one, which it returns to.

ClosedFinishing at the same vertex it started from.

The Two Questions

+5 XP to read

A walk permits everything, so the classification comes from what you take away.

Ban repeated edges. The journey may pass through a vertex more than once but may never travel along the same edge twice. That is a trail.

Ban repeated vertices. The journey may never return to a vertex it has already visited. That is a path.

These are genuinely different questions, not two strengths of one. A trail may cross itself at a vertex; a path may not.

Both restrictions have natural meanings. A trail is what a postal worker walks: every street once, and passing the same corner twice is unavoidable and harmless. A path is what a tourist wants: never doubling back on anything.

Every Path Is a Trail

+5 XP to read

One implication holds between the two, and it is worth being able to justify rather than remember.

Suppose a walk repeats an edge. That edge has two endpoints, and travelling along it a second time means arriving at both of those endpoints a second time. So a repeated edge forces a repeated vertex.

Turning that around: a walk with no repeated vertex can have no repeated edge. So every path is a trail.

The converse fails, and one example settles it. In a graph shaped like a figure eight, going round the first loop and then the second uses every edge once but visits the middle vertex three times. That is a trail and is not a path.

So path is the stronger condition, and "trail" is the weaker one that more journeys satisfy.

Closing the Journey

+5 XP to read

The third question is whether the journey returns to its starting vertex.

A closed trail is a circuit: no edge repeated, and it finishes where it began.

A closed path is a cycle: no vertex repeated, except that the last vertex is the first one again.

That exception in the definition of a cycle needs stating, because strictly a closed journey does repeat a vertex, namely its start. The starting vertex is the one permitted repetition, and every other vertex appears once.

So the triangle $A \to B \to C \to A$ is a cycle, since only $A$ appears twice and it does so as start and finish. The journey $A \to B \to C \to A \to D \to A$ is not a cycle, since $A$ appears three times and the second appearance is not the end.

Classifying in Practice

+5 XP to read

Given a walk, three checks settle its name.

List the edges used and look for a repeat. A repeat means it is not a trail, and therefore not a path, circuit or cycle either.

List the vertices visited and look for a repeat. Ignore a final return to the start for now.

Compare the first and last vertices to see whether it is closed.

Then read off the answer. No edge repeat and open gives a trail; also no vertex repeat gives a path. No edge repeat and closed gives a circuit; also no other vertex repeat gives a cycle.

Report the most specific name that applies. A cycle is also a circuit and also a trail and also a walk, all correctly, but calling it a walk when it is a cycle throws away everything the question was testing.

Where the Words Are Going

+5 XP to read

The next two lessons need only two of these four, and it is worth knowing which in advance.

An Eulerian trail is a trail that uses every edge of the graph exactly once. It is a trail rather than a path, and that is essential: a journey covering every street will nearly always revisit corners, so demanding no repeated vertex would make it impossible for almost every graph.

An Eulerian circuit is such a trail that also returns to its start.

The Königsberg bridge problem asks for one of these. Getting the word right matters there, because the question is about crossing every bridge once, not about visiting every part of the city once, and those are different requirements with different answers.

There is a corresponding pair of ideas about visiting every vertex once, named after Hamilton rather than Euler. They are beyond this focus area, but knowing they exist prevents the two families being confused.

Watch Me Solve It · 3 examples

Watch Me Solve It · Classifying three journeys

+15 XP per step

PROBLEM

A graph has vertices $A$, $B$, $C$, $D$ and edges $AB$, $BC$, $CD$, $DA$, $AC$. Classify each of $A \to B \to C \to D$, $A \to B \to C \to A \to D$ and $A \to B \to C \to D \to A$ as fully as possible.

1

The first journey

$\text{edges: } AB, BC, CD$

No edge repeats and no vertex repeats, and it starts at $A$ and ends at $D$, so it is open. It is a path, and therefore also a trail.
2

The second journey

$\text{edges: } AB, BC, CA, AD$

No edge repeats, so it is a trail. But $A$ appears twice, at the start and in the middle, so it is not a path. It ends at $D$, so it is open and not a circuit.
3

The third journey

$\text{edges: } AB, BC, CD, DA$

No edge repeats and it returns to $A$, so it is a circuit. Apart from the return to the start, no vertex repeats, so it is a cycle.
4

Give the most specific names

Report the strongest description that holds, since each of these also satisfies the weaker ones.

AnswerA path; a trail that is not a path; a cycle

Watch Me Solve It · A trail that is not a path

+15 XP per step

PROBLEM

In the graph with edges $PQ$, $QR$, $RP$, $PS$, $ST$, $TP$, find a trail that uses all six edges and is not a path, and explain why no path can use all six edges.

1

Describe the shape of the graph

The edges $PQ$, $QR$, $RP$ form one triangle and $PS$, $ST$, $TP$ form another, and the two triangles share only the vertex $P$. The graph is a figure eight.
2

Take one triangle then the other

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

This goes round the first triangle to $P$, round the second, and back.
3

Check it is a trail

$QR, \ RP, \ PT, \ TS, \ SP, \ PQ$

Six edges, all different, and they are all six edges of the graph. So it is a trail, and since it returns to $Q$ it is a circuit.
4

Check it is not a path

The vertex $P$ appears twice in the middle of the journey, once on arriving from $R$ and once on arriving from $S$. A path forbids that, so this trail is not a path.
5

Explain why no path can use all six edges

Any journey covering edges in both triangles must pass through $P$, the only vertex they share. Having entered and left each triangle, it must arrive at $P$ more than once, which a path forbids. So no path reaches all six edges.

Answer$Q \to R \to P \to T \to S \to P \to Q$ uses all six edges without repetition and visits $P$ twice

Watch Me Solve It · Finding a cycle of a given length

+15 XP per step

PROBLEM

In the graph with vertices $A$ to $E$ and edges $AB$, $BC$, $CD$, $DE$, $EA$, $AC$, find a cycle of length $3$ and a cycle of length $5$.

1

Look for a triangle

$A \to B \to C \to A$

Uses $AB$, $BC$ and $CA$, all of which exist. Three edges, so length $3$, and no vertex except $A$ repeats.
2

Look for a route around the outside

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

Uses $AB$, $BC$, $CD$, $DE$, $EA$. Five edges, so length $5$, and every vertex appears once apart from the return to $A$.
3

Confirm both are cycles

Each is closed, repeats no edge, and repeats no vertex other than its start. Both conditions hold, so both are cycles rather than merely circuits.
4

Note what is not possible

There is no cycle of length $4$ here, since any four-edge closed route would have to use $AC$ together with three of the outside edges, and no such combination closes up.

Answer$A \to B \to C \to A$ has length $3$; $A \to B \to C \to D \to E \to A$ has length $5$

Brain Trainer · 5 problems

Brain Trainer · Name the journey

5 problems

Five items. Give the most specific correct name in each case.

1 What is a walk with no repeated edge called?

The restriction is on edges.A trail
2 What is a walk with no repeated vertex called?

The restriction is on vertices, which is stronger.A path
3 What is a closed trail called?

Closing a trail gives the corresponding closed name.A circuit
4 Is every trail a path?

A trail may cross itself at a vertex.No
5 Is every path a trail?

Reusing an edge would mean revisiting its endpoints.Yes

Complete in your workbook.

Multiple Choice · 5 questions

MC1

The trail restriction

+10 XP

A trail is a walk in which:

MC2

The implication

+10 XP

Which statement is true?

MC3

The same edge, two names

+10 XP

In a graph with edges $AB$, $BC$, $CD$, $DA$, $BD$, the journey $A \to B \to D \to C \to B \to A$ is:

MC4

The cycle exception

+10 XP

In a cycle, the number of vertices that appear more than once is:

MC5

Which one Euler needs

+10 XP

A journey that uses every edge of a graph exactly once is called an Eulerian trail rather than an Eulerian path because:

Short Answer · 3 questions

Classify four journeys

+15 XP

SHORT ANSWER

A graph has vertices $A$, $B$, $C$, $D$, $E$ and edges $AB$, $BC$, $CA$, $CD$, $DE$, $EC$. Classify each of these as fully as possible: $A \to B \to C \to D$; $A \to B \to C \to A$; $A \to B \to C \to D \to E \to C \to A$; $A \to B \to C \to B \to A$.

Write your working in your book.

Justify the implication

+15 XP

SHORT ANSWER

Prove that every path is a trail, and give an explicit example of a trail that is not a path, describing the graph you use.

Write your working in your book.

Choose the right journey

+15 XP

SHORT ANSWER

For each task, state which of trail, path, circuit or cycle is required, and justify the choice: a street sweeper must clean every street once and return to the depot; a tourist wants to see four landmarks without passing any point twice; an inspector must walk every footbridge once and may finish anywhere.

Write your working in your book.

Stretch Challenge · How long can a cycle be?

+25 XP

CHALLENGE

In a graph with $n$ vertices, what is the greatest possible length of a cycle, and why? Then explain why a graph can have many cycles of different lengths, using the complete graph on four vertices as an example, and count how many cycles of length $3$ it contains.

Quick Review

recap

Trail bans edges, path bans vertices

A trail may cross itself at a vertex; a path may not. The path restriction is the stronger one.

Closing gives the other two names

A closed trail is a circuit; a closed path is a cycle. In a cycle the starting vertex is the only permitted repetition.

Every path is a trail

Repeating an edge repeats both of its endpoints, so no repeated vertex forces no repeated edge. The converse fails, as a figure-eight route shows.

Euler needs trails, not paths

Covering every edge usually forces a vertex to be passed more than once, so the vertex restriction has to be dropped for the next two lessons.

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