Walks, Trails, Paths, Cycles and Circuits

Walks

Definition: For a graph $G = (V(G), E(G))$, a Walk is defined as a sequence of alternating vertices and edges such as $v_0, e_1, v_1, e_2, ..., e_k, v_k$ where each edge $e_i = \{ v_{i-1}, v_i \}$. The Length of this walk is $k$.

For example, the graph below outlines a possibly walk (in blue). The walk is denoted as $abcdb$. Note that walks can have repeated edges. For example, if we had the walk $abcdcbce$, then that would be perfectly fine even though some edges are repeated.

Note that the length of a walk is simply the number of edges passed in that walk. In the graph above, the length of the walk is $abcdb$ is $4$ because it passes through $4$ edges.

Open / Closed Walks

Definition: A walk is considered to be Closed if the starting vertex is the same as the ending vertex, that is $v_0 = v_k$. A walk is considered Open otherwise.

For example, the follow graph shows a closed walk in green:

Notice that the walk can be defined by $cegfc$, and the start and end vertices of the walk is $c$. Hence this walk is closed.

Trails

Definition: A Trail is defined as a walk with no repeated edges.

So far, both of the earlier examples can be considered trails because there are no repeated edges. Here is another example of a trail:

Notice that the walk can be defined as $abc$. There are no repeated edges so this walk is also a trail.

Now let's look at the next graph:

Notice that this walk must repeat at least one edge.

Paths

Definition: A Path is defined as an open trail with no repeated vertices.

Notice that all paths must therefore be open walks, as a path cannot both start and terminate at the same vertex. For example, the following orange coloured walk is a path

because the walk $abcde$ does not repeat any edges.

Now let's look at the next graph with the teal walk. This walk is NOT a path since it repeats a vertex, namely the pink vertex $c$:

Cycles

Definition: A Cycle is defined as a closed trail where no other vertices are repeated apart from the start/end vertex.

Below is an example of a circuit. Notice how no edges are repeated in the walk $bcgfb$, which makes it definitely a trail, and that the start and end vertex $b$ is the same which makes it closed.

Circuits

Definition: A Circuit is a closed trail. That is, a circuit has no repeated edges but may have repeated vertices.

An example of a circuit can be seen below. Notice how there are no edges repeated in the walk $hbcdefcgh$, hence the walk is certainly a trail. Additionally, the trail is closed, hence it is by definition a circuit.