= Solution
Root the <tree> arbitrarily. For each <vertex> $v$, let $D_1(v)$ be the minimum <vertex cover> size in its descendant <subtree>, conditional on selecting $v$, and $D_0(v)$ the corresponding minimum conditional on omitting $v$. Process the <vertices> in <postorder traversal>. For every child $u$ of $v$,
$$
\boxed{D_1(v)=1+\sum_{u\text{ child of }v}\min\{D_0(u),D_1(u)\},\qquad D_0(v)=\sum_{u\text{ child of }v}D_1(u).}
$$
At a <leaf of a rooted tree>, the empty <sums> give $D_1=1,D_0=0$. Return \b[$\min\{D_0(r),D_1(r)\}$] at the root $r$.
For <algorithm correctness>, if $v$ is selected, each child <subtree> may independently use its cheaper state, since the connecting <edge> is already covered by $v$. If $v$ is omitted, each child must be selected to cover its connecting <edge>. Distinct child <subtrees> have no <edges> between them because the input is a <tree>. These observations prove the recurrences by <structural induction>. Each <edge> contributes constant work once, giving \b[$O(|V|)$ <time complexity> and $O(|V|)$ space] with <adjacency lists>. The single-vertex <tree> correctly has optimum zero. This is <minimum vertex cover of a tree> by <dynamic programming>.
Back to article page
