What is a Trail? | Graph Theory

What is a trail in the context of graph theory? That is the subject of today’s math lesson! Recall that a walk in a graph G is just any sequence of vertices in G where consecutive vertices are adjacent. A trail is the same thing except with the added restriction that no edge can be traversed multiple times. So if a and b are consecutive vertices in the trail, then a cannot follow b nor can b follow a at any other point in the sequence, because that would necessitate traversing the edge ab again. Let’s look at an example.

Suppose W = (a, b, c, d, e, a, d, c) is a walk in G. Then, W is not a trail because, while it is a sequence of vertices where consecutive vertices are adjacent, an edge is traversed multiple times in this walk, which is not allowed in a trail. Notice in W that the edge cd is traversed multiple times. That is why W is not a trail.

Let’s instead suppose W = (a, b, c, d, b, e, a) is a walk in G. Then, W is also a trail because it is a sequence of vertices where consecutive vertices are adjacent (we only know they are adjacent because we already assumed it was a walk, so we are assuming they are adajcent), and no edge is traversed multiple times. Notice that we do visit the vertices a and b multiple times in the trail W, but we do not traverse any edge multiple times, so it is indeed a trail.

Furthermore, we can say that W = (a, b, c, d, b, e, a) is a ‘closed’ trail because its end vertices are the same, just like with walks. Also as with walks, all vertices and edges traversed in the trail are said to ‘lie on’ the trail W.

Like with walks, an alternative way of defining trails, which is often used instead, is for them to be a sequence of alternating vertices and edges. In this way of defining a trail, the trail starts and ends with a vertex, but after a vertex you list the edge traveled, then the vertex you are on, then the edge traveled, and so on up until the final vertex you stop at. So remember our trail W = (a, b, c, d, b, e, a). If we were to write this trail using this alternative definition, we would write W = (a, ab, b, bc, c, cd, d, db, b, be, e, ea, a). This way of defining trails and walks lets the edges traversed be much more explicit, since they are listed out right in the sequence instead of being implied by the vertices traveled.

I hope you find this video helpful, and be sure to ask any questions down in the comments!

+WRATH OF MATH+

◆ Support Wrath of Math on Patreon:   / wrathofmathlessons  

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● Facebook:   / wrathofmath  
● Twitter:   / wrathofmathedu  

Music Channel:    / seanemusic