Minimum vertex cover of a tree ($D_0(v)={\sum }_u{D}_1(u),D_1(v)=1+{\sum }_u\min (D_0(u),D_1(u))$)

Root a finite tree, and let $D_0,D_1$ be the optimum vertex cover sizes of a descendant subtree conditional on excluding or including its root. Excluding a parent forces all children to be included; including it permits either child state. These facts prove the displayed recurrences by structural induction. Empty child sums give $D_0=0,D_1=1$ at a leaf of a rooted tree. Evaluating in postorder traversal and taking the smaller root state gives a linear-time dynamic programming algorithm.