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"?

  • 4
    $\begingroup$ You seem to have misunderstood something: the definitions in the book are the same as those given as current by Wikipedia. $\endgroup$ Oct 7, 2013 at 2:37
  • 1
    $\begingroup$ You may be right. Specifically, I only just realized that paths have distinct vertices, whereas trails have distinct edges. $\endgroup$ Oct 7, 2013 at 2:42
  • $\begingroup$ Indeed you are right, I misread the text. If you post your comment as an answer I'd gladly accept it. $\endgroup$ Oct 7, 2013 at 2:45
  • $\begingroup$ Done — and perhaps a little more clearly. $\endgroup$ Oct 7, 2013 at 2:47
  • $\begingroup$ 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..... $\endgroup$
    – Grimer
    Sep 24, 2018 at 18:34

5 Answers 5


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.


enter image description here

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)


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .