A walk is a sequence 
,
, 
, ..., 
of graph vertices 
and graph edges 
such that for 
, the edge 
has endpoints 
and 
(West 2000, p. 20). The length of a walk is its number of edges.
A 
-walk is a walk with first vertex 
and last vertex 
, where 
and 
are known as the endpoints. Every 
-walk contains a 
-graph path (West 2000, p. 21).
A walk is said to be closed if its endpoints are the same. The number of (undirected) closed 
-walks in a graph with adjacency
matrix 
is given by 
, where 
denotes the matrix trace.
In order to compute the number 
of 
-cycles,
all closed 
-walks that are not cycles
must be subtracted. Similarly, to compute the number 
of graph paths, all 
-walks that are not graph paths (because they contain redundant
vertices) must be subtracted (cf. Festinger 1949, Ross and Harary 1952).
For a simple graph (which has no multiple edges), a walk may be specified completely by an ordered list of vertices (West 2000, p. 20).
A trail is a walk with no repeated edges.
