درختی داریم که $n$ راس دارد. در هر مرحله می‌توانیم به ازای هر مولفه از این درخت دقیقا یکی از ۲ کار زیر را انجام دهیم.

• یک یال دلخواه را از مولفه حذف کنیم.
• همه‌ی برگ‌‌ها را در مولفه حذف کنیم.

دقت کنید که در یک مرحله می‌توان روی دو مولفه کار متفاوتی انجام داد. ثابت کنید:

1. به ازای هر درخت می‌توان مراحل را طوری انجام داد که در $O(\sqrt{n})$ مرحله همه‌ی یال‌ها حذف بشوند.
2. به ازای هر $n$ مثالی بزنید که به $\Omega(\sqrt{n})$ مرحله نیاز باشد تا همه‌ی یال‌ها حذف شوند.