Counting matchings and tree-like walks in regular graphs

The number of closed tree-like walks in a graph is closely related to the moments of the roots of the matching polynomial for the graph. Thus by counting these walks up to a given length it is possible to find approximations for the matching polynomial. This approach has been used in two separate problems involving asymptotic enumerations of 1-factorisations of regular graphs. Nevertheless, a systematic way to count the required walks had not previously been found.

In this paper we give an algorithm to count closed tree-like walks in a regular graph up to a given length. For small m, this provides expressions for the number of m-matchings in the graph in terms of the numbers of copies of certain small subgraphs that appear in the graph. We also find generating functions that isolate the contribution from the simplest kind of subgraph - namely those consisting of a single cycle of arbitrary length.