# Definition: Walks, Trails, and Paths

A walk in a digraph $$D(V,E,\alpha,\omega)$$ or an undirected graph $$G(V,E,\gamma)$$ is a non-empty, alternating succession of vertices $$v_i\in V$$ and edges $$e_i\in E$$ $W^k:=v_0e_0v_1e_1v_2e_2\ldots e_{k-1}x_{k},$ such that $$e_i=v_iv_{i+1}$$ for all $$i < k$$.

A trail is a walk, in which all the edges, but not necessarily all the vertices all distinct.

A path is a walk, in which all the edges and all the vertices are distinct. We denote the path by $$P^k:=x_0x_1\ldots x_{k-1}x_k$$.

The number $$k$$ of the edges in the walk (or the trail, or the path) is called its length.

Please note that for walks, (or trails or paths), $$k$$ is allowed to be zero; thus e.g. a walk with $$k$$ vertices $$W_k$$ has a length of $$k-1$$ edges; a path $$P^0$$ consists of just one vertex (and does not contain any edges).

#### Examples: In the undirected graph above:

• $$abcgfcdefghabcde$$ is a walk, but not a trail because the e.g. the edges $$gf$$, $$ab$$, etc. are passed more then once.
• $$abcdefcg$$ is a trail, but not a path because the vertex $$c$$ is passed more then once.
• $$abcdef$$ is a path (every edge and every vertex is passed exactly once). In the digraph above:

• there is no path from $$e$$ to $$a$$, however, $$ade$$ is a path from $$a$$ to $$e$$
• $$acbacbdeee$$ is a walk

Definitions: 1 2 3 4 5 6 7 8
Examples: 9
Lemmas: 10
Proofs: 11 12 13 14 15 16 17 18
Propositions: 19 20

Github: ### References

#### Bibliography

1. Aldous Joan M., Wilson Robin J.: "Graphs and Applications - An Introductory Approach", Springer, 2000
2. Diestel, Reinhard: "Graph Theory, 3rd Edition", Springer, 2005