# Definition:Walk (Graph Theory)/Length

< Definition:Walk (Graph Theory)(Redirected from Definition:Length of Walk)

Jump to navigation
Jump to search
*This page is about length of a walk in the context of Graph Theory. For other uses, see Length.*

## Definition

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.

### Zero Length Walk

A **zero length walk** is a **walk** which consists of one vertex.

## Examples

### Arbitrary Example 1

In the graph below:

the path $1, 3, 4$ has length $2$.

The vertex $5$ forms a zero length walk.

### Arbitrary Example 2

In the rooted tree below:

the path from $1$ to $9$ has length $4$.

## Sources

- 1977: Gary Chartrand:
*Introductory Graph Theory*: Chapter $10$: Graphs and Other Mathematics: $10.1$: Graphs and Matrices - 1979: John E. Hopcroft and Jeffrey D. Ullman:
*Introduction to Automata Theory, Languages, and Computation*... (previous) ... (next): Chapter $1$: Preliminaries: $1.2$ Graphs and Trees - 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**