A path in a graph 
is a subgraph of 
that is a path graph (West 2000, p. 20). The length of a path is the number of edges it contains.
In most contexts, a path must contain at least one edge, though in some applications (e.g., defining the path covering number), "degenerate" paths of length 0 consisting of a single vertex are allowed (Boesch et al. 1974).
An 
-path is a path whose endpoints (vertices of degree 1) are the vertices with distinct indices 
and 
. (The symbols 
and 
are also commonly used.) A single 
-path may be found in the Wolfram Language using FindPath[g, s, t], while FindPath[g, s, t, kspec, n] finds at most 
paths of length kspec (where kspec may be Infinity and 
may be All).
For a simple graph, a path is equivalent to a trail and is completely specified by an ordered sequence of vertices. For a simple graph 
, a Hamiltonian path is a path that includes all vertices of 
(and whose endpoints are not adjacent).
The number of (undirected) 
-walks from vertex 
to vertex 
in a graph with adjacency matrix 
is given by the 
element of 
(Festinger 1949). In order to compute the number 
of graph paths, all closed 
-walks that are not paths must be subtracted.
The first few matrices of 
-paths 
can be given in closed form by
 |  |  | (1) |
 |  |  | (2) |
 |  |  | (3) |
(Luce and Perry 1949, Katz 1950, Ross and Harary 1952, Perepechko and Voropaev), where 
is the matrix formed from the diagonal elements of 
and 
denotes matrix element-wise multiplication.
Furthermore, the number of 
-cycles is related to 
by
 | (4) |
where 
denotes the trace.
Giscard et al. (2016) gave the formula for the path matrix giving the number of 
-paths from 
to 
as
 | (5) |
where the sum is over connected induced subgraphs 
of 
containing both 
and 
, 
denotes the number of neighbors of 
in 
(namely vertices 
of 
which are not in 
and such that there exists at least one edge from 
to a vertex of 
), 
denotes the matrix trace, and 
is the 
th element of the 
th matrix power of the adjacency matrix of 
restricted to the connected induced subgraph 
, namely
 | (6) |
with 
.
Paths in a Graph." J. Graph Algorithms Appl. 11, 195-214, 2007.Ross, I. C. and Harary, F. "On the Determination of Redundancies in Sociometric Chains." Psychometrika 17, 195-208, 1952.Valiant, L. G. "The Complexity of Enumeration and Reliability Problems." SIAM J. Computing 8, 410-421, 1979.West, D. B.