TADM2E 5.13

1) We can determine that leafs should never be included into the cover. Therefore all leaves should be unmarked, which means that all of their parents should be marked. Now we remove all leaves from the tree and all of their parents, together with all of their edges. We then repeat this process on the modified tree.

2) We consider again the leafs, each is degree 1. For each leaf, if we consider its parent, its degree is the number of children + 1. It means that we have to choose between removing the n children of degree one or the parent of degree n+1. We remove the parent, mark the leafs as included, and recurse as in 1) above.