گراف $G$ با $n$ راس به ما داده شده است. ما درهر مرحله برای هر مولفه همبندی گراف، طولانی‌ترین مسیر را پیدا کرده و همه‌ی راس‌های آن را حذف می‌کنیم. این کار را برای گراف باقی‌مانده تکرار می‌کنیم. دقت کنید که یک مولفه‌ی گراف ممکن است بیش‌تر از یک طولانی‌ترین مسیر داشته باشد. در این صورت یکی از آن‌ها را به دلخواه انتخاب می‌کنیم.

توجه: در هر مرحله از هر مولفه یک مسیر حذف می‌شود.

1. ثابت کنید مستقل از این‌که در هر مرحله و در هر مولفه کدام طولانی‌ترین مسیر را انتخاب می‌کنیم، بعد از حداکثر $2\times \sqrt{n}$ مرحله کل گراف حذف می‌شود.
2. گرافی پیدا کنید که حتی با بهترین روش حذف نتوان تمام راس‌های آن را در کم‌تر از $log_3(n)$ مرحله کاملا حذف کرد (باید ثابت کنید که در آن گراف حداقل $log_3(n)$ مرحله لازم است.).

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