(closed) walk / trek / trail / path

Graph theory terminology is notoriously variable so the following definitions should be used with caution. In books, most authors define their usage at the beginning.

In a graph, multigraph or even pseudograph $G$ ,

• a walk of length $s$ is formed by a sequence of $s$ edges such that any two successive edges in the sequence share a vertex (aka node). The walk is also considered to include all the vertices (nodes) incident to those edges, making it a subgraph.

  In the case of a simple graph (i.e. not a multigraph) it is also possible to define the walk uniquely by the vertices it visits: a walk of length $s$ is then a sequence of vertices $\nu_0$ , $\nu_1$ , ... $\nu_s$ such that an edge $\nu_i\nu_{i+1}$ exists for all $0\le i\lt s$ . Again the walk is considered to contain those edges as well as the vertices.

• A trek is a walk that does not backtrack, i.e. no two successive edges are the same.

  For simple graphs this also implies $\nu_i \ne \nu_{i+2}$ for all $0\le i\le s-2$ .

• A trail is a walk where all edges are distinct, and
• a path is one where all vertices are distinct.

The walk, etc. is said to run from $\nu_0$ to $\nu_s$ , to run between them, to connect them etc. The term trek was introduced by Cameron [Cam94] who notes the lexicographic mnemonic $$ \hbox{\em paths\/} \;\subset\; \hbox{\em trails\/} \;\subset\; \hbox{\em treks\/} \;\subset\; \hbox{\em walks\/} $$ The other terms are fairly widespread, cf. [Wil02], but beware: many authors call walks paths, and some then call paths chains. And when edges are called arcs, a trek of length $s$ sometimes goes by the name $s$ -arc.

Note that for the purpose of defining connectivity any of these types of wanderings can be used; if a walk exists between vertices $\mu$ and $\nu$ then there also exists a path between them. And here we must allow $s=0$ to make ``are connected by a path'' an equivalence relation on vertices (in order to define connected components as its equivalence classes).

• A closed walk aka circuit of length $s\ne0$ is a walk where $\nu_0 = \nu_s$ ,
• a closed trek is a trek that's closed in the same way, and
• a closed trail likewise;
• a closed path aka (elementary) cycle is like a path (except that we only demand that $\nu_i$ for $0\le i\lt s$ are distinct) and again closed ($\nu_s$ again coincides with $\nu_0$ ).

Beware: cycles are often called circuits [Cam94]; the distinction between circuits and cycles here follows Wilson [Wil02]. These closed wanderings are often called after their length: $s$ -circuits, $s$ -cycles.

The case $s=0$ is excluded from these definitions; $1$ -cycles are loops so imply a pseudograph; $2$ -cycles are double edges implying multigraphs; so $3$ is the minimum cycle length in a proper graph.

Note also that in trivalent aka cubic graphs a closed trail is automatically a closed path: it is impossible to visit a vertex (in via edge $a$ , out via edge $b$ say) and visit it again (in via $c$ , out via $d$ ) without also revisiting an edge, because there are only three edges at each vertex.

• An open walk, open trek, open trail is one that isn't closed.
• An open path (sometimes open chain) is just a path as defined above (because a closed path isn't actually a path). Still, the term is useful when you want to emphasise the contrast with a closed path.

Bibliography

Cam94

PETER J. CAMERON, Combinatorics: topics, techniques, algorithms
Camb. Univ. Pr. 1994, ISBN0521457610,
http://www.maths.qmul.ac.uk/~pjc/comb/ (solutions, errata &c.)

Wil02

ROBERT A. WILSON, Graphs, Colourings and the Four-colour Theorem,
Oxford Univ. Pr. 2002, ISBN0198510624 (pbk),
http://www.maths.qmul.ac.uk/~raw/graph.html (errata &c.)