Walks in Graphs: Open, Closed, Trails, Paths, Circuits, and Cycles

Introduction

If graph theory is the study of maps, then a walk is the journey you take on that map. It is the most fundamental way to traverse a graph, and mastering it unlocks everything else: paths, shortest-path algorithms, Eulerian circuits, Hamiltonian cycles, and connectivity.

In this post we build the complete walk hierarchy from the ground up — starting with the most permissive definition and tightening the rules one step at a time until we reach the strictest concepts. Every term in the hierarchy adds exactly one restriction, and each restriction has a clear name.

What Is a Walk?

The Road Trip Analogy

Think of a graph as a road network:
- Vertices (dots) are cities
- Edges (lines) are highways connecting them

A walk is your road trip: the ordered sequence of cities and highways you travel, from start to finish.

To describe your trip precisely, you list every city in the exact order you visited it — and there must actually be a highway connecting each consecutive pair of cities. No teleporting.

Formal Definition

A walk in a graph $G = (V, E)$ is a finite sequence:

$$v_0,\ e_1,\ v_1,\ e_2,\ v_2,\ \ldots,\ e_k,\ v_k$$

where each $e_i = (v_{i-1}, v_i)$ is an edge in $E$. The walk starts at $v_0$ and ends at $v_k$.

In practice, since each edge is determined by its endpoints, we usually just write the vertex sequence:

$$v_0 \to v_1 \to v_2 \to \cdots \to v_k$$

The Two Rules of a Walk

1. Follow the edges: you can only move from $u$ to $v$ if the edge $(u, v)$ exists — adjacent vertices only.
2. That’s it. There are no other rules.

What this means in practice:
- ✅ You can repeat vertices
- ✅ You can repeat edges
- ❌ You cannot teleport to a non-adjacent vertex

The Length of a Walk

The length of a walk is the number of edges traversed — not the number of vertices visited.

$$\text{length} = k = |\text{edges in sequence}|$$

Since each edge connects two consecutive vertices:

$$\text{length} = (\text{number of vertices in sequence}) - 1$$

Important: if a vertex or edge appears multiple times in the sequence, it is counted each time.

The Base Graph

All the examples in this post use the following five-vertex neighbourhood graph. Take a moment to familiarise yourself with it.

• Vertices: A, B, C, D, E
• Edges: A–B, A–C, B–D, C–D, D–E
• Notice: there is no direct edge from A to E, from A to D, or from B to E.

Walk Examples

Example 1 — Open Walk: A → B → D → E

The orange edges show the traversal. Green = start, red = end.

Example 2 — Walk with a Repeated Edge: C → D → C → A

This walk is valid but it cannot be called a trail (see below) because edge C–D is used twice.

Example 3 — Closed Walk: A → B → D → C → A

The four edges of the square A–B–D–C form a perfect loop. Because no intermediate vertices or edges repeat, this is also a cycle (we’ll define that precisely below).

Example 4 — Invalid Walk: A → E → D

Attempting this would be “teleporting” — forbidden in graph traversal. Always check the edge actually exists before claiming a walk.

Open vs. Closed Walks

The first distinction we make after establishing a walk is whether it returns to where it started.

All further categories (trail, path, circuit, cycle) inherit this open/closed distinction.

The Walk Hierarchy

As we add restrictions to a walk, it earns a more specific name. The hierarchy flows like this:

Walk  (anything goes)
│
├── Open Walk ──────── Trail (no repeated edges)
│                          └── Path (no repeated vertices either)
│
└── Closed Walk ─────── Circuit (no repeated edges)
                             └── Cycle (no repeated vertices either, except start = end)

Open Walk Family

Trail — No Repeated Edges

Definition: An open trail is a walk where every edge is used at most once. Vertices may be revisited.

Think of hiking a trail system in a national park. You might pass through Base Camp (a vertex) twice, but you never hike the exact same dirt path (edge) twice.

This graph shows the trail A → B → C → D → B → E:

• Vertex B is visited twice — that is allowed in a trail
• Every edge (A–B, B–C, C–D, D–B, B–E) is used exactly once — no edge repeats
• Length = 5

Because the edge C–D→B brings us back through B, this is a trail but not a path.

Key distinction: A trail forbids repeated edges; a path forbids repeated vertices (which automatically forbids repeated edges too).

Path — No Repeated Vertices (or Edges)

Definition: A path is a walk where every vertex is visited at most once. Since each vertex appears once, edges cannot repeat either.

This is the strictest open walk — a clean route from start to finish with no backtracking and no crossing your own trail.

Path A → B → C → D → E:

• Every vertex visited exactly once ✓
• Every edge used exactly once ✓
• Length = 4
• The graph has additional edges (B–D, C–E) that are not part of the path — they exist but are not traversed

Key insight: Every path is a trail, but not every trail is a path.

Closed Walk Family

Circuit — Closed Walk, No Repeated Edges

Definition: A circuit is a closed walk where every edge is used at most once. Vertices may be revisited (except the mandatory start = end condition).

A circuit is the closed analogue of a trail: you wander around, never crossing the same bridge twice, and eventually return to your starting point.

Circuit A → B → C → D → A on a graph with additional edges (A–E, B–E, C–E):

• Starts and ends at A (green) ✓
• Edges A–B, B–C, C–D, D–A each used once ✓
• The extra edges (to E) exist in the graph but are not part of this circuit
• Length = 4

Cycle — Closed Walk, No Repeated Vertices or Edges

Definition: A cycle is a closed walk where every vertex is visited at most once, and every edge is used at most once — except that the starting vertex also appears at the end to close the loop.

A cycle is the closed analogue of a path. It forms a perfect ring: leave your starting point, visit entirely new vertices, and the only time you see a familiar face is when you arrive back at your starting point.

The 5-cycle $C_5$: A → B → C → D → E → A

• Starts and ends at A ✓
• Every intermediate vertex (B, C, D, E) visited exactly once ✓
• Every edge used exactly once ✓
• Length = 5

Key insight: Every cycle is a circuit, but not every circuit is a cycle. A circuit that revisits a vertex is not a cycle.

Complete Hierarchy Table

Subset relationships:
- Every path is a trail is a walk
- Every cycle is a circuit is a closed walk is a walk

Important Properties

Walk Length and Connectivity

A walk exists between two vertices $u$ and $v$ if and only if $u$ and $v$ are in the same connected component of the graph. If no walk exists between them, they are in different components.

This means you can use the existence of walks to test connectivity.

Shortest Walk = Shortest Path

The shortest walk between two vertices $u$ and $v$ is always a path (no repeated vertices). Why? If the walk visits any vertex twice, you could shortcut past the repeated portion and get a shorter walk. Therefore:

Theorem: The shortest walk between two vertices is a path, and its length equals the distance $d(u, v)$ in the graph.

This is the foundation of algorithms like BFS (Breadth-First Search) for finding shortest paths.

The Handshaking Connection

In a closed walk of length $k$ starting and ending at vertex $v$, the walk visits exactly $k$ edges. This has implications for Eulerian circuits — a circuit that uses every edge of the graph exactly once. Such a circuit exists if and only if the graph is connected and every vertex has even degree (a result we will explore in a future post).

Common Misconceptions

“A path and a walk are the same thing”

❌ No. A walk allows repeated vertices and edges; a path forbids both. Every path is a walk, but most walks are not paths.

“Closed walk and cycle mean the same thing”

❌ No. A closed walk just means it starts and ends at the same place — it may repeat vertices and edges freely. A cycle is a closed walk that repeats nothing (except the mandatory start = end).

“A trail and a path are the same thing”

❌ No. A trail allows vertices to repeat; a path does not.

Practice Problems

Problem 1: Identifying Walk Types

Question: Consider the graph with edges: A–B, B–C, C–D, D–A, B–D. Classify each sequence:

(a) A → B → C → D → A
(b) A → B → D → A
(c) A → B → C → D → B → A
(d) A → B → D → B → C

Problem 2: Walk Length

Question: A walk visits the vertex sequence: P → Q → R → P → Q → S. What is the length of this walk?

Problem 3: Does a Trail Exist?

Question: A graph has vertices {1, 2, 3, 4} and edges {1–2, 2–3, 3–4, 4–1, 1–3}. Does a trail from 1 to 4 using all 5 edges exist?

Problem 4: Shortest Path

Question: In the base graph (A–B, A–C, B–D, C–D, D–E), what is the length of the shortest walk from A to E?

Problem 5: Cycle Detection

Question: Does the base graph contain a cycle? If yes, give one example.

Applications

Routing and Navigation

Every GPS navigation system finds the shortest path between two locations — a direct application of the path definition. BFS finds shortest paths in unweighted graphs; Dijkstra’s algorithm handles weighted graphs.

Eulerian Circuits

An Eulerian circuit is a circuit that traverses every edge of the graph exactly once. The famous Königsberg Bridge Problem (Euler, 1736) asked whether such a circuit existed — its solution founded graph theory. The answer depends entirely on vertex degrees, connecting the walk hierarchy to degree theory.

Hamiltonian Cycles

A Hamiltonian cycle is a cycle that visits every vertex exactly once. Unlike Eulerian circuits, determining whether a Hamiltonian cycle exists is NP-complete — one of the hardest problems in computer science. The Traveling Salesman Problem (TSP) is essentially “find the shortest Hamiltonian cycle.”

Connectivity

Two vertices are connected (in the same component) if and only if a walk exists between them. Algorithms like DFS and BFS determine connectivity by searching for walks.

Distance in a Graph

The distance between two vertices $u$ and $v$ in a graph $G$, written $d(u, v)$, is the length of the shortest path from $u$ to $v$.

$$d(u, v) = \min \{ \text{length of a path from } u \text{ to } v \}$$

If no path exists (i.e., $u$ and $v$ are in different components), then $d(u, v) = \infty$.

Key points:
- Distance is measured in edges (not vertices), consistent with the walk length convention.
- The shortest walk between two vertices is always a path (revisiting a vertex can only increase length).
- Distance is the central quantity behind all shortest-path algorithms: BFS, Dijkstra, Bellman-Ford.

Worked Example

Using the base graph (edges A–B, A–C, B–D, C–D, D–E), the distances from vertex A are:

Node colours encode distance level: green = 0, orange = 1, teal = 2, blue = 3.

There is no direct edge A–E, so the only routes go through D. The shortest is 3 hops — matching what Problem 4 above computed.

Properties of Distance

Graph distance satisfies the three axioms of a metric:

The triangle inequality expresses the intuitive idea that going through an intermediate vertex $v$ can only make the route at least as long as the direct route from $u$ to $w$.

Note: In directed graphs, symmetry may not hold — it might be faster to go from $u$ to $v$ than from $v$ to $u$, or one direction may be unreachable entirely.

Diameter

The diameter of a connected graph is the largest distance between any pair of vertices:

$$\text{diam}(G) = \max_{u, v \in V} d(u, v)$$

In the base graph the diameter is $d(A, E) = 3$ — A and E are the furthest-apart pair. Diameter characterises how “spread out” a graph is; social networks typically have small diameter (the famous “six degrees of separation”).

Key Takeaways

1. A walk is any vertex sequence following edges — vertices and edges may repeat freely.
2. Length = number of edges traversed (count repeats).
3. Open walk: start ≠ end. Closed walk: start = end.
4. Trail = open walk with no repeated edges.
5. Path = open walk with no repeated vertices (strictest open walk).
6. Circuit = closed walk with no repeated edges.
7. Cycle = closed walk with no repeated vertices (strictest closed walk).
8. Every path is a trail. Every cycle is a circuit. Neither implication reverses.
9. The shortest walk between two vertices is always a path; its length is the distance $d(u,v)$.

Explore Further

Use the GraphArena Playground to experiment:
- Draw a random connected graph and trace a walk that repeats an edge — confirm it is not a trail
- Find a trail that is not a path (visit a vertex twice, never reuse an edge)
- Find the shortest path between two vertices and verify its length equals the graph distance
- Try to construct a circuit that is not a cycle (it must revisit a vertex mid-way)
- Build a cycle on 4, 5, and 6 vertices and notice the pattern

The walk hierarchy — Walk → Trail → Path and Walk → Circuit → Cycle — is the vocabulary that powers every graph algorithm you will ever encounter.