زاریچ که زندگی خود را وقف شکست ویروس کرونا کرده است، از روی نقشه‌ی شهرهای آلوده یک گراف ساده‌ی ۳۰ رأسی ساخته است. او می‌خواهد رأس‌های این گراف را به تعدادی بخش افراز کند، طوری که بین رأس‌های درون هر بخش هیچ یالی وجود نداشته باشد (هر بخش یک مجموعه‌ی مستقل باشد). او پس از بررسی‌های فراوان فهمیده است که می‌تواند رأس‌های گراف را به ۱۰ بخش با شرایط بالا تقسیم کند، اما امکان انجام این کار برای ۹ بخش وجود ندارد.
الف) ثابت کنید گراف زاریچ دوری با حداکثر ۸ رأس دارد. (۱۰ نمره)
ب) ثابت کنید گراف زاریچ دوری با حداکثر ۵ رأس دارد. (۱۰ نمره؛ با حل این بخش، نمره‌ی بخش الف را نیز دریافت می‌کنید.)
پاسخ