The Number of $f$-Matchings in Almost Every Tree is a Zero Residue

Abstract

For graphs $F$ and $G$ an $F$-matching in $G$ is a subgraph of $G$ consisting of pairwise vertex disjoint copies of $F$. The number of $F$-matchings in $G$ is denoted by $s(F,G)$. We show that for every fixed positive integer $m$ and every fixed tree $F$, the probability that $s(F,\mathcal{T}_n) \equiv 0 \pmod{m}$, where $\mathcal{T}_n$ is a random labeled tree with $n$ vertices, tends to one exponentially fast as $n$ grows to infinity. A similar result is proven for induced $F$-matchings. As a very special special case this implies that the number of independent sets in a random labeled tree is almost surely a zero residue. A recent result of Wagner shows that this is the case for random unlabeled trees as well.