Walks, Trails, Paths, Circuits, and Cycles Revision Notes for VCE SSCE General Mathematics

Walks, Trails, Paths, Circuits, and Cycles

Understanding how to move through a graph is essential for solving many real-world problems, such as designing delivery routes or finding the most efficient way to visit several locations. This section introduces five important ways to describe movement through a graph: walks, trails, paths, circuits, and cycles.

Introduction to movement in graphs

Many practical problems can be modelled using graphs. For example, you might need to design a postal delivery route or find the most efficient way to visit several locations. To solve these problems, you need to understand the different ways you can move around a graph.

infoNote

Throughout this section, we'll use a graph representing walking tracks in Sherbrooke Forest to explore these concepts. This real-world example will help you understand how these abstract concepts apply to practical situations.

This graph represents a series of tracks in Sherbrooke Forest connecting:

A picnic ground (vertex $P$ )
A waterfall (vertex $W$ )
A very old tree (vertex $T$ )
A fern gully (vertex $F$ )
Two entry/exit points: Gate 1 (vertex $G1$ ) and Gate 2 (vertex $G2$ )

The edges represent the physical tracks connecting these locations. For example, edge $WP$ represents the track between the waterfall and the picnic ground.

Walks, trails and paths

These three concepts describe different types of journeys through a graph, each with its own rules about which edges and vertices can be revisited.

Walks

A walk is the most general type of movement through a graph. It's any journey that moves from one vertex to another along the connecting edges.

chatImportant

Walk

A walk is a sequence of edges linking successive vertices, that connects two different vertices in a graph.

When there's no confusion, you can describe a walk simply by listing the vertices visited in order.

infoNote

In a walk, you can repeat both edges and vertices as many times as you like. This makes it the most flexible type of movement through a graph.

Example: A walk in the forest

Using the forest track graph, here's an example of a walk:

$G1-P-F-G2-T-G2-F$

This walk starts at Gate 1 and ends at the fern gully. Notice that:

The edge between $G2$ and $T$ is travelled along twice (shown by the double red arrows)
Vertex $G2$ is visited twice
This is perfectly acceptable in a walk

Trails

A trail is more restrictive than a walk. While you can still revisit vertices, you cannot use the same edge more than once.

chatImportant

Trail

A trail is a walk with no repeated edges.

infoNote

Key Difference from Walks

Unlike a walk, a trail does not allow repeated edges. However, vertices can still be visited multiple times, making it useful for situations where you need to use different routes to reach the same location.

Example: A forest trail

Using the forest track graph, here's an example of a trail:

$G1-P-F-G2-T-W-P-G2$

This trail has no repeated edges. However, notice that:

Vertex $P$ appears twice
Vertex $G2$ appears twice
This is allowed in a trail—only edges cannot repeat

Paths

A path is the most restrictive type of walk. Neither edges nor vertices can be repeated (except you need at least two vertices to make a path).

chatImportant

Path

A path is a walk with no repeated edges and no repeated vertices.

A path represents the most efficient route between two locations, with no backtracking or revisiting.

Example: A path in the forest

Using the forest track graph, here's an example of a path:

$G1-F-P-W-T-G2$

This path has no repeated edges or vertices. It's a direct route from Gate 1 to Gate 2.

Worked example: Identifying walks, trails and paths

lightbulbExample

Worked Example: Identifying walks, trails and paths

The graph below shows how seven vertices are connected. One walk is described as $A-D-C-F-E-B$ . Does this walk represent a trail or a path?

Solution

Let's check the conditions:

Does it start at one vertex and end at a different vertex? Yes ( $A$ to $B$ )
Are there any repeated edges? No
Are there any repeated vertices? No

Since this walk has no repeated edges and no repeated vertices, it must be a path.

Exam tip: To identify the type of walk, always check in this order:

Does it start and end at different vertices? (If yes, it's a walk, trail, or path)
Are there repeated edges? (If no, it's a trail or path)
Are there repeated vertices? (If no, it's a path)

Circuits and cycles

A walk, trail, or path can start and end at the same vertex. When this happens, we call it a closed walk, trail, or path. Closed trails and closed paths are so important that they have special names: circuits and cycles.

Circuits

A circuit is a closed trail—it starts and ends at the same vertex with no repeated edges.

chatImportant

Circuit

A circuit is a walk that starts and ends at the same vertex and has no repeated edges.

infoNote

Circuits are useful for modelling situations where you need to return to your starting point, such as a delivery route that begins and ends at a depot, or a security patrol that covers multiple locations before returning to base.

Example: A circuit in the forest

Using the forest track graph, here's an example of a circuit:

$G1-F-P-W-T-G2-P-G1$

This circuit:

Starts and ends at vertex $G1$
Has no repeated edges
Visits vertex $P$ twice (this is allowed in a circuit)

Cycles

A cycle is a closed path—the cleanest possible loop through a graph.

chatImportant

Cycle

A cycle is a walk that starts and ends at the same vertex, has no repeated edges and has no repeated vertices.

Key Point: In a cycle, the first and last vertex are the same (because it's a closed walk), but this is the only vertex that can repeat. All other vertices must be unique.

Example: A cycle in the forest

Using the forest track graph, here's an example of a cycle:

$G2-P-W-T-G2$

This cycle:

Starts and ends at vertex $G2$
Has no repeated edges
Has no repeated vertices (except $G2$ , which is both the start and end point)

Worked example: Identifying circuits and cycles

lightbulbExample

Worked Example: Identifying circuits and cycles

The graph below shows how seven vertices are connected. One walk is described as $F-E-B-C-F$ . Does this walk represent a circuit or a cycle?

Solution

Let's check the conditions:

Does it start and end at the same vertex? Yes (vertex $F$ )
Are there any repeated edges? No
Are there any repeated vertices (other than the start/end)? No

Since this walk starts and ends at the same vertex, has no repeated edges, and has no repeated vertices (except the first/last vertex), it must be a cycle.

Exam tip: The key difference between circuits and cycles:

Circuit: Can revisit vertices (but not edges)
Cycle: Cannot revisit vertices (except the start/end point)

Summary of the five types

bookmarkSummary

Comparison of All Five Types

Here's a helpful comparison of all five types:

Type	Start/End	Repeated Edges?	Repeated Vertices?
Walk	Different vertices	Yes	Yes
Trail	Different vertices	No	Yes
Path	Different vertices	No	No
Circuit	Same vertex	No	Yes
Cycle	Same vertex	No	No (except start/end)

Key Pattern: Notice that each type becomes progressively more restrictive:

Walk → Trail: No repeated edges allowed
Trail → Path: No repeated vertices allowed
Circuit is to cycle as trail is to path

bookmarkSummary

Key Points to Remember

A walk is any journey through a graph connecting different vertices—edges and vertices can repeat
A trail is a walk where no edge repeats (but vertices can)
A path is a walk where neither edges nor vertices repeat
A circuit is a closed trail that returns to its starting vertex with no repeated edges
A cycle is a closed path that returns to its starting vertex with no repeated edges or vertices
When identifying types, check: same start/end? → repeated edges? → repeated vertices?

Walks, Trails, Paths, Circuits, and Cycles (VCE SSCE General Mathematics): Revision Notes