Definition:Walk (Graph Theory)

Definition

A walk on a graph is:

an alternating series of vertices and edges

beginning and ending with a vertex

in which each edge is incident with the vertex immediately preceding it and the vertex immediately following it.

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 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.