سوال ۱

سعی کنید تعداد زیردرخت‌های القایی با دقیقا ۳ برگ را بشمارید.

می‌توان تعداد چنین زیردرخت‌هایی را با انتخاب سه راس به عنوان برگ شمرد. اما حالاتی که یک راس در مسیر میان دو راس دیگر است باید حذف شود.

بر حسب طول قطر، تعداد حالات انتخاب سه راس نامطلوب در راهنمایی فوق را تخمین بزنید.

اگر طول قطر $k$ باشد، حداکثر $$\binom{n}{2} \times (k-2)$$ انتخاب نامطلوب داریم.

فرض خلف کنید طول قطر از $\Omega(n)$ نباشد. تعداد زیردرخت‌ها را به کمک راهنمایی‌های فوق تخمین بزنید.

چون طول قطر از $\Omega(n)$ نیست، پس از $\frac{n}{100}$ کمتر است.

پس تعداد زیردرخت‌ها حداقل برابر $$\binom{n}{3} - \binom{n}{2} \times \frac{n}{100}$$ است. این مقدار از $10n^2$ بیشتر است.