# In graph theory, what is the difference between a "trail" and a "path"?

I'm reading Combinatorics and Graph Theory, 2nd Ed., and am beginning to think the terms used in the book might be outdated. Check out the following passage:

If the vertices in a walk are distinct, then the walk is called a path. If the edges in a walk are distinct, then the walk is called a trail. In this way, every path is a trail, but not every trail is a path. Got it?

On the other hand, Wikipedia's glossary of graph theory terms defines trails and paths in the following manner:

A trail is a walk in which all the edges are distinct. A closed trail has been called a tour or circuit, but these are not universal, and the latter is often reserved for a regular subgraph of degree two.

Traditionally, a path referred to what is now usually known as an open walk. Nowadays, when stated without any qualification, a path is usually understood to be simple, meaning that no vertices (and thus no edges) are repeated.

Am I to understand that Combinatorics and Graph Theory, 2nd Ed. is using a now outdated definition of path, referring to what is now referred to as an open walk? What are the canonical definitions for the terms "walk", "path", and "trail"?

• You seem to have misunderstood something: the definitions in the book are the same as those given as current by Wikipedia. Oct 7, 2013 at 2:37
• You may be right. Specifically, I only just realized that paths have distinct vertices, whereas trails have distinct edges. Oct 7, 2013 at 2:42
• Indeed you are right, I misread the text. If you post your comment as an answer I'd gladly accept it. Oct 7, 2013 at 2:45
• Done — and perhaps a little more clearly. Oct 7, 2013 at 2:47
• Here is the lecture note from my graph theory class, the author and Prof is Dr.Charles Suffel, I added some examples aside to help classify path and trail. path&trail Feel free to correct me if I am wrong, I am actually a CS girl..... Sep 24, 2018 at 18:34

You seem to have misunderstood something, probably the definitions in the book: they’re actually the same as the definitions that Wikipedia describes as the current ones.

A walk of length k is a non-empty alternating sequence of vertices and edges in G.

A walk is a trail if any edge is traversed at most once.

A trail is a path if any vertex is visited at most once except possibly the initial and terminal vertices when they are the same.

Today I also faced the same problem for reading these very first concepts. My understanding is as follows.

Path: A path is a simple graph whose vertices can be ordered so that two vertices are adjoint iff they are constitutive in the list.

Walk: it is a list of vertices and edges $v_0, e_1, v_1, \dots, e_k, v_k$ for $1\le i \le k$, $e_i$ has an endpoints $v_{i-1}, v_i$.

Trial: It is an walk with no repeated edge.

In a trail all edges have direction and the end of one edge leads into the start of a new edge.In a path the same applies,but the same vertex can't be visited more than once which can occur in a trail. Walk: any sequence starting and ending with vertices and having at least one edge between any two vertices and all edges being incident to vertices before and next to them
e.g. 1: [a, e1, b, e1, a, e2, c, e3, d]

Trail: a walk with none edges repeated
e.g. 2 [a, e1, b, e5, e, e6, d]
e.g. 3 [a, e2, c, e3, d, e9, g, e10, e, e6, d, e4, b]

Path: a walk with none vertices repeated with the exception of first and last vertex of this walk
e.g. 4 [a, e1, b, e4, d]

e.g. 1 is walk but neither trail (due to edge e1 repeated) nor path (due to vertex a repeated)
e.g. 2 is a trail and also a path (none edge or vertex repeated)
e.g. 3 is a trail but not a path (due to vertex d repeated)
e.g. 4 is a trail and also a path (none edge or vertex repeated)

(it's not possible to have a path which is not a trail as that requires the condition of a walk having not repeated vertices but repeated edges which is impossible because if an edge is repeated then at least one of it's incident vertices must be repeated)