The induced forest polynomial of a simple graph 
with 
vertices is
 |
(1)
|
where 
counts the 
-element
subsets 
of the vertex set for which
![G[S]](/images/equations/InducedForestPolynomial/Inline6.svg)
is an induced forest. The empty
set contributes 
. Barton et al. (2022) call this generating
function the acyclic polynomial, a name
also used for the different matching polynomial.
The value 
counts all induced forests, distinguished by their
vertex sets. Its polynomial
degree is the maximum number of vertices in an
induced forest, hence 
minus the feedback
vertex set number.
Every forest 
on 
vertices satisfies
 |
(2)
|
For a cycle graph 
with 
, only the full vertex set
is excluded, so
 |
(3)
|
For a complete graph 
with 
, only subsets of size at
most 2 contribute, giving
 |
(4)
|
The graph disjoint union of 
and 
satisfies
 |
(5)
|
