A graph 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).
In a simple graph, a path has no repeated vertices and is completely specified by an ordered sequence of
vertices. A trail has no
repeated edges, but may repeat vertices.
A Hamiltonian path is a path that includes all
vertices of the graph 
. Its endpoints may be adjacent.
The number of (undirected) 
-walks from vertex 
to vertex 
in a graph with adjacency
matrix 
is given by the 
element of 
(Festinger 1949). To compute the number 
of graph paths, all 
-walks that repeat a vertex
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, Voropaev and Perepechko), where 
is the matrix
formed from the diagonal elements of 
and 
denotes matrix element-wise multiplication.
Furthermore, for 
, 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.Voropaev,
A. N. and Perepechko, S. N. "The Number of Fixed Length Cycles in
an Undirected Graph: Explicit Formulae in Case of Small Lengths." Discrete
Contin. Models Appl. Comput. Sci. No. 2, 6-12, 2012.West, D. B.