اپدیا

بر روی رنگ راس ریشه حالت‌بندی کنید

اگر ریشه قرمز باشد و قصد داشته باشیم زیرمجموعه‌ی پیدا شده‌ی مطلوب مسئله قرمز باشد، در هر یک از دو زیر درخت حاصل از حذف ریشه، می‌بایست به دنبال چه زیرمجموعه‌ای از رئوس باشیم؟ در صورتی که بخواهیم زیردرخت انتخابی آبی باشد چطور؟

با استفاده از دو راهنمایی بالا، از استقرا استفاده کنید.

بر روی $p+q$ استقرا بزنید.

اگر ریشه قرمز باشد، در زیر درخت‌های چپ و راست به دنبال یافتن زیر مجموعه‌ای مطلوب از راس‌ها خواهیم بود که درختی با ارتفاع $p-1$ قرمز باشد، یا زیر درختی با ارتفاع $q$ به رنگ آبی. اگر ریشه آبی باشد چطور؟