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"?
$\endgroup$ 54 Answers
$\begingroup$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.
$\endgroup$ $\begingroup$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.
$\endgroup$ $\begingroup$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.
$\endgroup$ $\begingroup$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.
$\endgroup$
