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.
