المپدیا

ابتدا توجه کنید که اگر پاسخ مسئله $m$ باشد، هر گراف $n$ راسی و $m$ یالی باید همبند باشد.

پس بنا بر راهنمایی اول،‌ حداقل ${n-1\choose{2}}+1$ یال نیاز داریم

به مثال نقضی برای عدد به دست آمده در راهنمایی ۲ فکر کنید.

آیا در گراف غنی، راسی می‌تواند درجه یک باشد؟ با این نکته مثال نقض راهنمایی ۲ را بیابید.

حال سعی کنیم اثبات کنیم پاسخ مسئله برابر با${n-1\choose{2}}+2$ است.

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

وقتی تعداد یال‌های گرافی که در موردش صحبت می‌کنیم زیاد است و نزدیک حداکثر تعداد یال‌هاست، ایده‌ی بدی نیست که به مکمل آن فکر کنیم.

وقتی در گراف مسئله ${n-1\choose{2}}+2$ یال وجود دارد، در مکمل آن چند یال وجود دارد؟ در نتیجه چند مولفه‌ی همبندی داریم؟

از قضیه‌ی «اگر در گراف مکمل G، قطر بزرگ‌تر مساوی ۳ باشد آنگاه در G قطر کوچک‌تر مساوی سه است» استفاده کنید.

سعی کنید $g(5)$ را بیابید و بر حسب گراف آن، پاسخ را حدس بزنید.

داریم $g(5)=6$. مثال‌های قابل بسط آن را بیابید و سعی کنید مثالی غیر پیچیده برای $n$ های فرد پیدا کنید.

برای $n=5$، پاپیون (گرافی که از دو مثلث با یک راس مشترک تشکیل شده) مثال مناسبی به نظر می‌رسد. آیا می‌توانید دو راس دیگر به آن اضافه کنید که شرایط مسئله حفظ شود؟ سعی کنید اثبات کنید این مثال برای تمام $n$ های فرد قابل بسط است و صدق می‌کند.

راحت‌ترین راه برای افزایش تعداد راس‌های مثال برای ساختن مثال $n$ های زوج چیست؟ به مثال $g(4)$ دقت کنید.

حال که به پاسخ دست یافته‌ایم (تعدادی مثلث که همگی در یک راس مشترکند و اگر تعداد راس‌ها زوج بود، یکی از مثلث‌ها را به مثال $g(4)$ تبدیل کنید) باید نشان دهیم تعداد یال‌ها از این کمتر نمی‌شود.

گراف $G$ که $n$ راس دارد و غنی است را در نظر بگیرید. به حداقل مجموع اعداد دنباله‌ درجه‌ی $G$ فکر کنید.

آیا می‌توان زیرمجموعه‌ی $A$ (به تعریف مسئله) از رئوس را طوری انتخاب کرد که به ازای هر راس مجبور به حذف حداقل یک یال متصل به آن باشیم؟

عملیات راهنمایی ۷، باعث چه تغییری در دنباله‌ی درجات می‌شود؟

پس از عملیات ۷، مجموع درجات گراف برای همبند بودن حداقل باید چقدر باشد؟ پس مجموع درجات گراف قبل این عملیات حداقل چقدر بوده؟