# 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. – Brian M. Scott Oct 7 '13 at 2:37
• You may be right. Specifically, I only just realized that paths have distinct vertices, whereas trails have distinct edges. – modocache Oct 7 '13 at 2:42
• Indeed you are right, I misread the text. If you post your comment as an answer I'd gladly accept it. – modocache Oct 7 '13 at 2:45
• Done — and perhaps a little more clearly. – Brian M. Scott Oct 7 '13 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..... – W2SAT Sep 24 '18 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.