سوال چهارم (۴۰ نمره)

در یک گراف ساده، سختی یک مجموعه‌ی $S$ از رأس‌ها را تعداد یال‌هایی از این گراف تعریف می‌کنیم که حداقل یکی از دو سرشان، عضو $S$ باشد. به عنوان مثال در گراف زیر، سختی مجموعه‌ی $\{a, b, c\}$ برابر ۴ است.

یک گراف ساده را در نظر بگیرید که ۱۰۰۰ یال دارد و درجه‌ی هر رأس آن حداکثر ۴ است. در این گراف، ۳۰۰ رأس به رنگ قرمز، و بقیه‌ی رأس‌ها به رنگ آبی هستند. به یک مجموعه از رأس‌ها، قرمز می‌گوییم اگر همه‌ی اعضای آن مجموعه به رنگ قرمز باشند. ثابت کنید یک مجموعه‌ی قرمز ۳۰ رأسی با سختی حداکثر ۱۰۰ وجود دارد.

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