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.
How the names differ.
NameRepeated edges?Repeated vertices?Finishes where it started?
Open walkallowedallowedno
Open trailnoallowedno
Open pathnonono
Closed walkallowedallowedyes
Circuit (closed trail)noallowedyes
Cycle (closed path)noonly the start, at the endyes

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.

Interactive

Trace some routes

Trace AA–BB–CC–DD, then BB–CC–EE–BB, then BB–CC–EE–BB–AA–FF–BB. Which ones repeat a vertex? Which repeat an edge? Which finish where they started?

Worked example

Walk, trail, path, circuit or cycle?

  • Simple familiar

For the graph shown, give the most specific name for each route.

(a) AA–BB–CC–DD

(b) AA–BB–EE–FF–BB–CC

(c) BB–CC–BB–EE

(d) BB–CC–EE–BB

(e) BB–CC–EE–BB–AA–FF–BB

6 steps

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

Method

  1. Open or closed?

  2. A repeated edge means it is only a walk.

  3. No repeated edge but a repeated vertex: a trail (a circuit if closed).

  4. 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 FF–BB–CC–EE–BB–AA?

Choose one answer

In the graph above, what is the most specific name for the route AA–BB–EE–FF–AA?

Choose one answer

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

  • Complex familiar

The graph shows the roads between eight towns, AA to HH.

(a) Is the graph connected?

(b) Identify every bridge.

(c) Road DEDE is closed for repairs. Can every town still be reached from every other town? Explain.

5 steps

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

Method

  1. Edges that lie on a cycle are not bridges.

  2. 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 PP, QQ, RR, SS and TT, with lines PQPQ, QRQR, RPRP, RSRS and STST. Which lines are bridges? Select all that apply.

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.

Lesson 5 of 80% read

Save your progress with a free account