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

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

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

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

• سوال بعد
• سوال قبل