INTRODUCTION TO MATCHING POLYNOMIALS

A matching of a graph G is a spanning subgraph of G in which every component is either a node or an edge of G. With every matching M, we can associate a monomial Π(M) = Παwα where wα is a weight associated with the component and the product is taken over all components in M. The matching polynomial of G is the polynomial ΣΠ(M), where the summation is taken over all matchings in G. Since the edges of a matching are independent edges of the graph, the coefficients of the terms of the matching polynomial represent the number of sets of independent edges of various cardinalities in G. © 1979.