There are various ways to move from vertex to vertex along the edges of a graph.

A walk is a sequence of vertices such that each successive pair of vertices is adjacent. If no edge is repeated on a walk, then it is a trail. If no vertex is repeated on a trail, then it is a path.

A circuit is a trail which starts and finishes at the same vertex. If no vertex is repeated in the circuit (except for the start/end vertex), then it is a cycle.

On the above graph, A -> C -> E is not a walk, as there is no edge between C and E.

D -> C -> B -> C is a walk, but it is not a trail as edge BC is repeated.

E -> B -> A -> C -> B is a trail as no edges are repeated, but it is not a path as vertex B is repeated.

A -> C -> D and C -> B -> E -> A are both paths.

E -> B -> A -> C -> B -> D -> E is a circuit, but it is not a cycle as vertex B is repeated.

A -> B -> C -> A is a cycle.

The length of a route is the number of edges traversed, so for instance E -> B -> A -> C -> B is a trail of length 4.

Exercise

Answers