= Solution
Choose a root. For each vertex $v$, define $I(v)$ as the maximum size in its descendant <subtree> when $v$ is included, and $O(v)$ as that size when $v$ is excluded. For its children $w$,
$$
\boxed{I(v)=1+\sum_{w}O(w),\qquad
O(v)=\sum_w\max\{I(w),O(w)\}.}
$$
A leaf has $I=1,O=0$. If $v$ is included, all its children must be excluded. If $v$ is excluded, either child state is allowed. Different child subtrees have no edges between them because the graph is a <tree>, so their contributions can be optimized independently. This proves the recurrence by <structural induction>.
Evaluate the two states in <postorder traversal>. At root $r$, the answer is $\max\{I(r),O(r)\}$. For reconstruction, pick an attaining root state; an included vertex forces every child to its excluded state, while an excluded vertex permits each child to choose its larger state. Record the included vertices during this second traversal, breaking ties consistently.
With <adjacency lists>, rooting, state evaluation and reconstruction each take \b[$O(|V|+|E|)=O(n)$ time], with $O(n)$ stored states and output. This is <maximum independent set in a tree>.
The source describes an <independent set> as a proper subset. For a tree with at least one edge, every independent set is automatically proper, so the algorithm meets that convention. If it is enforced literally for the single-vertex tree, return the empty set of size zero there; the usual non-strict subset convention would instead return its one vertex.
Back to article page
