Školjka

Označimo sa $m$ broj dinastičkih čvorova u šumi. Svakom dinastičkom čvoru $a_i$ pridružimo skup sebe i njegovih potomaka $S_i$. (Potomak je extended succesor) Također, svakom dinastičkom čvoru pridružimo skup $V_i = \{k \ | \ a_i \in S_k, k \neq i \}$. Za svaki čvor koji ima djecu, odaberimo lijevo i desno dijete tog čvora. Na stablu vršimo sljedeći algoritam: Dok postoji, odaberimo dinastički čvor $a_i$ takav da $|V_i| = 1$ (takav očito postoji ako nisu svi $V_i$ prazni). Neka $a_j \in V_i$. Iz skupa $S_j$ uklonimo $a_i$, njegovo lijevo dijete i sve potomke tog djeteta, a iz skupa $S_i$ desno dijete $a_i$ i sve potomke tog djeteta. "Osvježimo" skupove $V_k$ za sve $k$. Nakon ovoga, vrijedi $|V_i| = 0$ i $S_i \cap S_j = \emptyset$ Također, primijetimo da $S_i$ sadrži $a_i$, njegovo lijevo dijete i potomke tog djeteta (njih barem $k$) pa $|S_i| \geqslant k+2$. Analogno, $|S_j| \geqslant k+2$. Algoritam očito terminira ($|V_1| + ... + |V_m|$ se smanjuje) te nakon njegovog izvođenja su skupovi $S_i$ disjunktni i vrijedi $|S_i| \geqslant k+2, \forall i$. Prema tome $n \geqslant |S_1| + ... + |S_m| \geqslant m(k+2)$ pa $m \leqslant \dfrac{n}{k+2}$, što je i trebalo pokazati.