Classify a route: walk, trail, path, circuit or cycle

Classifying a route

A route is a walk only when every consecutive pair is joined by an edge. After that, check whether it is open or closed, whether an edge repeats and whether an intermediate vertex repeats

1. Check adjacency Every consecutive pair in the listed sequence must be an edge \(\displaystyle AB,BC\in E\;\Rightarrow\;A\!-!B\!-!C\text{ is a walk}\)
2. Check the endpoints Different endpoints make an open route, while equal endpoints make a closed route \(\displaystyle A\!-!B\!-!C:\;A\ne C\;\Rightarrow\;\text{open}\)
3. Check repeated edges A walk with no repeated edge is a trail; a closed trail is a circuit \(\displaystyle AB,BC,CD\text{ distinct}\;\Rightarrow\;\text{trail}\)
4. Check repeated vertices An open trail with no repeated vertices is a path, and a closed trail with no repeated intermediate vertex is a cycle \(\displaystyle A\!-!B\!-!C\!-!A\;\Rightarrow\;\text{cycle}\)

Worked example

Classify the route A to B to C to A to D to E to A in a graph containing each listed edge

1. \(\displaystyle AB,BC,CA,AD,DE,EA\text{ are all edges}\)Every consecutive pair is joined, so the sequence is a walk
2. \(\displaystyle A=A\;\Rightarrow\;\text{closed}\)The route starts and finishes at A
3. \(\displaystyle AB,BC,CA,AD,DE,EA\text{ are all different}\;\Rightarrow\;\text{trail}\)No edge is used more than once
4. \(\displaystyle A\text{ is an intermediate repeated vertex}\;\Rightarrow\;\text{circuit, not cycle}\)The repeated intermediate A prevents the closed trail from being a cycle

Common mistakes

Difficulty levels

Questions about this topic

In this chapter