One would think that by analogy with the matching-generating polynomial, independence polynomial,
etc., a path polynomial whose coefficients are the numbers of paths of length 
would be defined. Although such a polynomial
does not appear to have been defined previously in the literature, it is defined
in this work.
The path polynomial, perhaps defined here for the first time, is therefore the polynomial
 |
(1)
|
whose coefficients 
give the number of simple paths of length 
present in a graph 
on 
nodes.
An empty graph has the zero polynomial as its path polynomial. For a graph with at least one edge, since
the smallest possible path has length 1, the path polynomial has polynomial
degree at least 1. In particular, 
, where 
is the edge count of a graph
.
For a graph on 
vertices, 
gives the number of Hamiltonian paths. Therefore,
the graph is traceable iff 
, or equivalently iff the degree
of its path polynomial is 
.
Since path counts in a disconnected graph are the sum of path counts in its connected components, the path polynomial is additive over connected components.
For three common graph families, the path polynomials have the forms
 |  |  |
(2)
|
 |  |  |
(3)
|
 |  |  |
(4)
|
Here paths are unoriented, so a path and its reversal are counted only once. Unlike the s-t path polynomial, these polynomials record path lengths rather than products of edge labels.
