# 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.