A 
-matching in a graph 
is a set of 
edges, no two of which have a vertex in common (i.e., an independent edge set of size 
). Let 
be the number of 
-matchings of the graph 
, with 
(since the empty set consisting of no edges is always a 0-matching) and 
the edge count of 
. Then the matching-generating polynomial directly encodes the numbers of 
-independent edge sets of a graph 
and is defined by
 | (1) |
where 
is the matching number of 
.
The matching-generating polynomial is multiplicative with respect to disjoint unions of graphs, so for graphs 
and 
,
 | (2) |
where 
denotes a graph union.
The matching-generating polynomial 
is related to the matching polynomial 
by
 | (3) |
(Ellis-Monaghan and Merino 2008) and
 | (4) |
The matching-generating polynomial is closely related to the independence polynomial. In particular, since independent edge sets in the line graph 
correspond to independent vertex sets in the original graph 
, the matching-generating polynomial of a graph 
is equal to the independence polynomial of the line graph of 
(Levit and Mandrescu 2005).
A graph 
has a perfect matching iff
 | (5) |
where 
is the vertex count of 
.
Precomputed matching-generating polynomials for many named graphs in terms of a variable 
will be obtainable using GraphData[graph, "MatchingGeneratingPolynomial"][x].
The following table summarizes closed forms for the matching-generating polynomials of some common classes of graphs. Here, 
is a confluent hypergeometric function of the second kind, 
is a Laguerre polynomial, and 
is a Lucas polynomial.
