Definition:Walk (Graph Theory)

This page is about walk in the context of graph theory. For other uses, see walk.

Definition

Let $G = \struct {V, E}$ be a graph.

A walk $W$ on $G$ is:

an alternating sequence of vertices $v_1, v_2, \ldots$ and edges $e_1, e_2, \ldots$ of $G$

beginning and ending with a vertex

in which edge $e_j$ of $W$ is incident with the vertex $v_j$ and the vertex $v_{j + 1}$.

A walk between two vertices $u$ and $v$ is called a $u$-$v$ walk.

To describe a walk on a simple graph it is sufficient to list just the vertices in order, as the edges (being unique between vertices) are unambiguous.

A closed walk is a walk whose first vertex is the same as the last.

That is, it is a walk which ends where it starts.

An open walk is a walk whose first vertex and last vertex are distinct.

That is, it is a walk which ends on a different vertex from the one where it starts.

The length of a walk (or a path, or a trail) is the number of edges it has, counting repeated edges as many times as they appear.

A walk is said to be of infinite length if and only if it has infinitely many edges.

Some sources refer to a walk as a path, and use the term simple path to define what we have here as a path.

Results about walks in the context of graph theory can be found here.