# Definition:Walk

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

### Closed

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.

### Open

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.

## Length

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** iff it has infinitely many edges.

## Also known as

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

## Also see

- Definition:Trail: a
**walk**in which all edges are distinct.

- Definition:Path (Graph Theory): a
**walk**in which all vertices are distinct.

## Sources

- Gary Chartrand:
*Introductory Graph Theory*(1977)... (previous)... (next): $\S 2.3$: Connected Graphs - Ephraim J. Borowski and Jonathan M. Borwein:
*Dictionary of Mathematics*(1989)