Dowód poprawności algorytmu zachłannego dla minimalnego pokrycia wierzchołka drzewa

Istnieje chciwy algorytm znajdowania minimalnego pokrycia wierzchołka drzewa, które korzysta z przejścia DFS.

1. Dla każdego liścia drzewa wybierz jego element nadrzędny (tzn. Jego element nadrzędny znajduje się w minimalnej osłonie wierzchołków).
2. Dla każdego węzła wewnętrznego:
   jeśli nie zostanie wybrane żadne z jego elementów podrzędnych, wybierz ten węzeł.

Jak udowodnić, że ta chciwa strategia daje optymalną odpowiedź? Czy nie ma pokrywy wierzchołków mniejszej niż ta, którą wytwarza powyższy algorytm?

$C$$C$$X$$X$$X$

$C$$C$$C$

$|M| \leq |C|$$M$$C$