The structure and maximum number of maximum independent sets in trees

Abstract A subset of vertices is a maximum independent set if no two of the vertices are joined by an edge and the subset has maximum cardinality. in this paper we answer a question posed by Herb Wilf. We show that the greatest number of maximum independent sets for a tree of n vertices is magnified image We give the families of trees on which these maxima are achieved. Proving which trees are extremal depends upon the structure of maximum independent sets in trees. This structure is described in terms of adjacency rules between three types of vertices, those which are in all, no, or some maximum independent sets. We show that vertices that are in some but not all maximum independent sets of the tree are joined in pairs by the α‐critical edges (edges whose removal increases the size of a maximum independent set). The number of maximum independent sets is shown to depend on the structure within the tree of the α‐critical edges.