Course contentsShow
← Mathematics
Lesson 2657 of 3,12153. Graph TheoryFree lesson

Walks, Trails, and Paths

Define walks, trails, and paths in graphs; understand the hierarchy of these concepts and their basic properties.

Walks, Trails, and Paths

What you'll learn: You'll understand the three fundamental ways to traverse a graph and how they differ by repetition rules.

The Core Idea

When you move through a graph from vertex to vertex along edges, you're creating a sequence of vertices and edges. Graph theory distinguishes three increasingly strict types of such sequences:

  • Walk: Any sequence of vertices where each consecutive pair is connected by an edge. You can repeat both vertices and edges as many times as you want.
  • Trail: A walk in which no edge is repeated (but vertices may repeat).
  • Path: A trail in which no vertex is repeated either (except possibly the first and last in a closed path).

Think of it like exploring a city: a walk lets you wander freely, crossing the same streets and revisiting corners. A trail means you never use the same street twice, though you might return to the same intersections. A path is the most direct route—you visit each intersection at most once.

The Hierarchy

Every path is a trail (no repeated edges or vertices), and every trail is a walk (no repeated edges). But not every walk is a trail, and not every trail is a path.

Example: In a triangle graph with vertices A, B, C:

  • Walk: A → B → C → A → B (repeats edge AB)
  • Trail: A → B → C → A (forms a cycle, no edge repeated)
  • Path: A → B → C (no vertices or edges repeated)

Key Takeaway: Walks are the most general traversal; trails forbid edge repetition; paths forbid both edge and vertex repetition—they form a strict hierarchy of movement constraints in graphs.