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.