Trail in a graph
= Trail in a graph
= Trail
{synonym}
A <trail> is a <walk> whose <edge> <sequence> $e_1,\ldots,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 is
$$
B,BC,C,CA,A,AD,D,DE,E,EA,A,AF,F.
$$
Its 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.https://people.math.binghamton.edu/zaslav/Oldcourses/581.S99/notes.html[Thomas Zaslavsky, Supplementary Notes for Graduate Graph Theory: trails and paths]{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.