Matching Polynomial (idea)

The matching polynomial of a graph is based on the number of distinct matchings (assuming the nodes are labeled) of the graph that have k edges within them. Let M(G,k) be the number of matchings containing k edges. The simple form of the matching polynomial is:

MP(G) = Sum(i) M(G,i) w^|V|-i

The traditional form of the matching polynomial is: MP(G) = Sum(i) M(G,i) w₁^|V|-2*i w₂ⁱ

Note M(G,k) = 0 if k > |V|/2.

Some examples:

• MP(K_j,k) = Sum(i<=j,i<=k) C(j,i) C(k,i) i! w^j+k-2i
• MP(K_n) = Sum(i <= (n/2)) (C(n,2i) (2i)! / (i! 2ⁱ) w^{n - 2i}
• MP(P_n) = w MP(P_n-1) + w MP(P_n-2)

Some basic properties:

• The w^|V| term always has a coefficient of 1.
• The w^|V|-1 term always has a coefficient of |E|, the number of edges.