Walk

Definition

A walk is a sequence of vertices and edges in a graph, where each edge's endpoints are the vertices that precede and follow it in the sequence. A walk can contain repeated vertices and edges.

5 Must Know Facts For Your Next Test

1. A walk can start and end at any vertex in the graph.
2. The length of a walk is determined by the number of edges it contains.
3. An open walk starts and ends at different vertices, while a closed walk starts and ends at the same vertex.
4. Every path and cycle in a graph is also a walk, but not every walk is necessarily a path or cycle.
5. Infinite walks are possible in graphs with infinite vertices or edges.

Review Questions

• What distinguishes an open walk from a closed walk?
• How do you determine the length of a walk?
• Can a walk contain repeated vertices and edges?

Related terms

Path:

A sequence of distinct vertices connected by edges without repetition.

Cycle:

A closed path where only the first and last vertices are the same.

Trail:

A type of walk where no edge is repeated, though vertices may be.