# Definition:Walk (Graph Theory)

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

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

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

- 1977: Gary Chartrand:
*Introductory Graph Theory*... (previous) ... (next): $\S 2.3$: Connected Graphs - 1989: Ephraim J. Borowski and Jonathan M. Borwein:
*Dictionary of Mathematics*... (previous) ... (next):**walk** - 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 2.3.4.1$: Free Trees - 1998: David Nelson:
*The Penguin Dictionary of Mathematics*(2nd ed.) ... (previous) ... (next):**walk** - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next):**walk** - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next):**walk**(in graph theory) - 2021: Richard Earl and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(6th ed.) ... (previous) ... (next):**walk**(in graph theory)