المپدیا

برای اثبات کمینگی، یک قطر به طول چهار در نظر بگیرید. هر راس دیگر گراف به چند راس از این قطر می‌تواند متصل باشد؟

پاسخ راهنمایی ۱: هر راس خارج قطر به دقیقا ۳ راس از قطر یال خواهد داشت.

راس‌ها را بر حسب نحوه‌ی یال داشتن به قطر دسته بندی کنید. چند دسته خواهیم داشت؟

پاسخ راهنمایی ۳: سه دسته. رئوسی که به سه راس اول، دوم یا سوم قطر متصل هستند.

ثابت کنید در صورت تهی بودن مجموعه‌ی رئوسی که به سه راس میانی قطر یال دارند، تعداد یال‌های گراف ماکسیمال می‌تواند کمتر بشود.

تنها یال‌هایی که در گراف وجود ندارند، کدام دسته یال‌ها هستند؟ تعداد آن‌ها را به چه نحو می‌توان بیشینه کرد؟

به کمک ساختار شکل گرفته در اثبات سعی کنید مثال نیز ارائه دهید.

برای راه حلی دیگر، به درخت $BFS$ گراف فکر کنید و راهنمایی‌های فوق را اعمال کنید.