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).
In the undirected graph above:
In the digraph above:
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
