On the Number of Independent Sets in a Tree

Abstract

We show in a simple way that for any $k,m\in{\Bbb N}$, there exists a tree $T$ such that the number of independent sets of $T$ is congruent to $k$ modulo $m$. This resolves a conjecture of Wagner (Almost all trees have an even number of independent sets, Electron. J. Combin. 16 (2009), # R93).