Difference Between Walk, Trail, and Path in a Graph

A walk is a finite sequence of edges where each consecutive edge is adjacent or identical (loops). It can be represented as $$ v_0 \rightarrow v_1 \rightarrow v_2 \rightarrow ... \rightarrow v_n $$ or more compactly as $$ v_0, v_1, v_2, ... , v_n $$. The length or cardinality of a walk is determined by the number of edges it contains.

In a walk, both vertices and edges can be repeated.

If the first and last vertex of the walk are the same $ v_0 = v_n $, it is called a closed walk or a circuit. 

For example, this graph consists of 4 vertices and 5 edges. The sequence A,B,C,A,B,D is an example of a walk. The length of the walk is 5 because there are five edges in the sequence. Note that the vertices A and B are repeated, and the edge AB is also repeated in the sequence.

The sequence A,B,C,A,B,D,C,A is a closed walk because the first and last vertex coincide (A).

A walk where all edges are distinct is called a trail.

In a trail, the first and last vertex can also be the same $ v_0 = v_n $, in which case it is called a closed trail.

For example, the sequence B,C,A,B,D is an example of a trail. In this sequence, no edge is repeated. Note that in a trail, vertices can be repeated. In the sequence shown, the vertex B is repeated twice.

The sequence A,B,C,A,B,D,C,A is a closed walk because the first and last vertex coincide (A).

A walk where all vertices are distinct is called a path.

Even in this case, the first and last vertex of a path can be the same $ v_0 = v_n $, and it is called a closed path or a cycle.

For example, the sequence A,B,D,C is a path because the vertices do not repeat in the sequence.

The sequence A,B,D,C,A is a cycle or closed path because the first and last vertex coincide (A).

Therefore, trails and paths are subsets of walks.