Lesson 5 of 8 · 16 min
Walks, trails, paths, circuits and cycles
Describe routes through a graph precisely — walks, trails and paths, open or closed, circuits and cycles — and recognise connected graphs and bridges.
What you will be able to do
- Define walk, trail and path, and say whether a route is open or closed.
- Recognise circuits (closed trails) and cycles (closed paths).
- Give the most specific name for a route through a graph.
- Recognise a connected graph, and identify the bridges in a graph.
A jogger, a tourist and a delivery driver all travel through networks, but they care about different things. The jogger is happy to run the same track twice. The tourist wants to see each place only once. The driver needs to finish back at the depot.
The words in this lesson describe a route by what it repeats and where it finishes. They are the vocabulary for the rest of the topic, so they need to be exact.
The graph used throughout this lesson.
Definition
Walk, trail and path
- A walk is a sequence of vertices in which each vertex is joined to the next by an edge. Vertices and edges may repeat.
- A trail is a walk with no repeated edges. Vertices may repeat.
- A path is a walk with no repeated vertices — and so no repeated edges either.
Definition
Open and closed, circuits and cycles
A route is open if it finishes at a different vertex from where it started, and closed if it finishes where it started.
- A closed walk returns to its start.
- A closed trail is called a circuit: it returns to its start with no repeated edges.
- A closed path is called a cycle: it returns to its start with no repeated edges, and no vertex repeated except that it finishes where it started.
| Name | Repeated edges? | Repeated vertices? | Finishes where it started? |
|---|---|---|---|
| Open walk | allowed | allowed | no |
| Open trail | no | allowed | no |
| Open path | no | no | no |
| Closed walk | allowed | allowed | yes |
| Circuit (closed trail) | no | allowed | yes |
| Cycle (closed path) | no | only the start, at the end | yes |
Key idea
The names nest inside each other
Every path is a trail, and every trail is a walk. Every cycle is a circuit, and every circuit is a closed walk. When you classify a route, give the most specific name that fits.
Trace –––, then –––, then ––––––. Which ones repeat a vertex? Which repeat an edge? Which finish where they started?
Worked example
Walk, trail, path, circuit or cycle?
For the graph shown, give the most specific name for each route.
(a) –––
(b) –––––
(c) –––
(d) –––
(e) ––––––
Step 1: Ask three questions of each route
Does it finish where it started (closed) or somewhere else (open)? Does it repeat an edge? Does it repeat a vertex, other than finishing where it started?
Step 2: (a) A–B–C–D
Open, with no repeated edges and no repeated vertices: an open path.
Step 3: (b) A–B–E–F–B–C
Open. The edges , , , and are all different, but vertex appears twice: an open trail, not a path.
Step 4: (c) B–C–B–E
Edge is used twice: an open walk, not a trail.
Step 5: (d) B–C–E–B
Closed, with no repeated edges and no vertex repeated except the start: a cycle (a closed path).
Step 6: (e) B–C–E–B–A–F–B
Closed with no repeated edges, but it also passes through in the middle: a circuit (a closed trail), not a cycle.
Try it yourself first, then check the working one step at a time.
Answer
(a) Open path. (b) Open trail. (c) Open walk. (d) Cycle. (e) Circuit.
Method
Open or closed?
A repeated edge means it is only a walk.
No repeated edge but a repeated vertex: a trail (a circuit if closed).
No repeated vertex: a path (a cycle if closed).
Watch out for
Calling (e) a cycle. A cycle may only return to its starting vertex at the very end.
Calling (b) a path because no edge repeats. A path must not repeat a vertex.
In the graph above, what is the most specific name for the route –––––?
In the graph above, what is the most specific name for the route ––––?
Definition
Connected graphs and bridges
A graph is connected if there is a path between every pair of vertices. A graph in two or more separate pieces is not connected.
A bridge is an edge whose removal would disconnect the graph. An edge that lies on a cycle is never a bridge, because the rest of the cycle still joins its ends.
Worked example
Finding the bridges in a road network
The graph shows the roads between eight towns, to .
(a) Is the graph connected?
(b) Identify every bridge.
(c) Road is closed for repairs. Can every town still be reached from every other town? Explain.
Step 1: Check whether the graph is connected
From you can reach and , then along , and from the towns , , and . Every town can be reached, so the graph is connected.
Step 2: Use cycles to rule edges out
An edge that lies on a cycle is never a bridge, because the rest of the cycle still links its two ends.
If edge is on a cycle, going the long way round the cycle still gets you from to .
Step 3: Rule out the edges on cycles
, and lie on the cycle –––. , , and lie on the cycle ––––. None of these is a bridge.
Step 4: Test the edges that are left
Removing separates , and from the other towns. Removing cuts off . So the bridges are and .
Step 5: Answer part (c)
lies on the cycle ––––, so it is not a bridge. Traffic can detour –––, and every town can still be reached.
Try it yourself first, then check the working one step at a time.
Answer
(a) Yes, the graph is connected. (b) and . (c) Yes: is not a bridge, because it lies on the cycle ––––, so ––– is a detour.
Method
Edges that lie on a cycle are not bridges.
For each remaining edge ask: if it were removed, could its two ends still reach each other?
Watch out for
Overlooking an edge to a vertex of degree 1. Removing it isolates that vertex, so it is a bridge.
A rail network has stations , , , and , with lines , , , and . Which lines are bridges? Select all that apply.
Common mistake
Path or cycle? Circuit or cycle?
- A path never returns to a vertex. A route that comes back to its start is closed, so call it a cycle (if nothing else repeats), not a path.
- A closed route that passes through some vertex twice along the way is a circuit, not a cycle — even if no edge repeats.
Exam tip
Questions often say "write down a cycle" or "identify a bridge". Give a route as a vertex sequence, such as RWPDR, and check it against the definition before you move on: for a cycle, only the first and last vertices may be the same.
Summary
A walk may repeat anything; a trail repeats no edge; a path repeats no vertex.
Open routes finish somewhere new; closed routes finish where they started.
A circuit is a closed trail; a cycle is a closed path (only the start vertex repeats, at the end).
A connected graph has a path between every pair of vertices.
A bridge is an edge whose removal disconnects the graph; edges on a cycle are never bridges.
Finished the lesson?
Try the 3 quick checks above and the lesson completes itself, or mark it complete now.