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.