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 ,

• a walk of length is formed by a sequence of 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 is then a sequence of vertices , , ... such that an edge exists for all . 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 for all .

• 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 to , to run between them, to connect them etc. The term trek was introduced by Cameron [Cam94] who notes the lexicographic mnemonic

-arc

Note that for the purpose of defining connectivity any of these types of wanderings can be used; if a walk exists between vertices and then there also exists a path between them. And here we must allow 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 is a walk where ,
• 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 for are distinct) and again closed ( again coincides with ).

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: -circuits, -cycles.

The case is excluded from these definitions; -cycles are loops so imply a pseudograph; -cycles are double edges implying multigraphs; so 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 , out via edge say) and visit it again (in via , out via ) 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.)