Walk
A walk of length k in a graph G is a succession of k edges of G of the form uv, vw, wx, . . . , yz.We denote this walk by uvwx . . yz and refer to it as a walk between u and z.
Trail and Path
If all the edges (but no necessarily all the vertices) of a walk are different, then the walk is called a trail. If, in addition, all the vertices are difficult, then the trail is called path.
-
The walk vzzywxy
is a trail since the vertices y and z both occur twice.
- The walk vwxyz is a path since the walk has no repeated vertices.