(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 suchthat any two successive edges in the sequence share a vertex (aka node).The walk is also considered to include all the vertices (nodes) incidentto those edges, making it a subgraph.

  In the case of a simple graph (i.e. not a multigraph) it is alsopossible to define the walk uniquely by the vertices it visits: awalk of length $s$ is then a sequence of vertices ${\nu }_0$,${\nu }_1$, … ${\nu }_s$ such that an edge ${\nu }_i{\nu }_{i+1}$ existsfor all . Again the walk is considered to contain thoseedges 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⩽i⩽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 }_{\mathrm{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

$$\text{𝑝𝑎𝑡ℎ𝑠}\subset \text{𝑡𝑟𝑎𝑖𝑙𝑠}\subset \text{𝑡𝑟𝑒𝑘𝑠}\subset \text{𝑤𝑎𝑙𝑘𝑠}$$

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 defineconnected components as its equivalence classes).

• A closed walk aka circuit of length $s\ne 0$ 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 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’tclosed.

• An open path (sometimes open chain) is just a path asdefined above (because a closed path isn’t actually a path). Still,the term is useful when you want to emphasise the contrast with aclosed path.