Paths and Walks

Let u and υ be vertices of a simple graph G. A path P from u to υ is a sequence of vertices u ₀, u ₁, ..., u_k such that u = u ₀, υ = u_k , u_i → u _{i + 1}, and all the u_i are distinct vertices. The length of a path P is ℓ(P), the number of edges it uses. In this example, ℓ(P) = k, and P is called a uυ -path of length k. A u ₀-path of length 4 is illustrated in Figure 2.1, with dashed edges.