Trail in a graph

A trail is a walk whose edge sequence $e_1,\dots ,e_m$ has no repetitions. Its vertices may repeat, including its first and last vertices. The zero-length walk is a trail because it repeats no edge. Every graph path is a trail, but the converse fails: the trail in the shared example isIts six edges $BC,CA,AD,DE,EA,AF$ are pairwise distinct, although $A$ occurs twice. Visiting a junction again and traversing a road segment again are different events.^[ref]

In an undirected graph, traversing $AB$ and then $BA$ repeats the same edge; direction of travel does not give it a new identity. In a multigraph with distinct parallel edges $p,q$ joining $X$ and $Y$, the closed walk $(X,p,Y,q,X)$ is a trail, whereas $(X,p,Y,p,X)$ is not. Both have the same vertex sequence $X,Y,X$. In a directed graph, separate directed edges $X\to Y$ and $Y\to X$ may instead be used once each; record their identities and obey their directions. Thus testing a trail means checking the actual edge records, not merely checking consecutive endpoint labels.

For a finite graph, a trail has length at most $|E|$; unrestricted walks can have arbitrarily large length whenever a positive-length closed walk exists, since it can be repeated. An Eulerian trail is the special trail that uses every edge, so its length is exactly $|E|$. Our length-six trail omits $AB$ and is therefore not an Eulerian trail. In a road-inspection model, a trail describes servicing its selected segments once while allowing returns to junctions; requiring service of every segment leads to the Eulerian trail question. If extra travel between serviced segments is necessary, the complete journey can be a walk even when each segment is serviced only once. This distinction keeps the service requirement separate from the route actually travelled.