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.