 Maximum independent set in a tree

Root a finite tree. The two dynamic programming states are the optimal size in the descendant subtree when its root $v$ is included, $I(v)$, or excluded, $O(v)$. The sums run over its children. Inclusion forces every child to be excluded; exclusion permits each child's better state. Child subtrees have no edges between them, which proves independence of these choices. The leaf states are $I=1,O=0$, and the root's better state gives the optimum.

A postorder traversal computes the states in $O(n)$ time and storage. Reconstruct a set by following an attaining root choice and the same child constraints, breaking ties arbitrarily. The empty and singleton cases use the ordinary non-strict subset convention.