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**_{1}^{|V|-2*i} w_{2}^{i}

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^{i}) 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.