A k-matching in a graph G is a set of k edges, no two of which have a vertex in common (i.e., an independent edge set of size k). Let Φ_k be the number of k-matchings of the graph G, with Φ_0(G) = 1 (since the empty set consisting of no edges is always a 0-matching) and Φ_1(G) = m the edge count of G. Then the matching-generating polynomial directly encodes the numbers of k-independent edge sets of a graph G and is defined by M(x) = sum_(k = 0)^(ν(G)) Φ_k x^k, where ν(G) is the matching number of G.

independence polynomial | independent edge set | matching | matching number | matching polynomial