A Note on Independent Sets in Trees

We give a simple graph-theoretical proof that the largest number of maximal independent vertex sets in a tree with n vertices is given by \[ m( T ) = {cases} 2k - 1 + 1& {if } n = 2k, \\ 2^k & {if } n = 2k + 1, {cases}\] a result first proved by Wilf [SIAM J. Algebraic Discrete Methods, 7 (1986), pp. 125–130]. We also characterize those trees achieving this maximum value. Finally we investigate some related problems.