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

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).

Precomputed matching-generating polynomials for many named graphs in terms of a variable
will be obtainable using GraphData[graph,
"MatchingGeneratingPolynomial"][x].

Ellis-Monaghan, J. A. and Merino, C. "Graph Polynomials and Their Applications II: Interrelations and Interpretations." 28 Jun 2008.
http://arxiv.org/abs/0806.4699.Levit,
V. E. and Mandrescu, E. "The Independence Polynomial of a Graph--A Survey."
In Proceedings of the 1st International Conference on Algebraic Informatics. Held
in Thessaloniki, October 20-23, 2005 (Ed. S. Bozapalidis, A. Kalampakas,
and G. Rahonis). Thessaloniki, Greece: Aristotle Univ., pp. 233-254, 2005.