On the Number of $F$-Matchings in a Tree

Hiu-Fai Law


We prove that for any integers $k,m>0$ and any tree $F$ with at least one edge, there exists a tree whose number of $F$-matchings is congruent to $k$ modulo $m$ as well as an analogous result for induced $F$-matchings. This answers a question of Alon, Haber and Krivelevich (The number of $F$-matchings in almost every tree is a zero residue, Electron. J. Combin. 18 (2011), #P30).

Full Text: