المپدیا

ابتدا مسئله را برای $k=n-2$ بررسی کنید. برای آنکه عدد همبندی یک واحد افزوده شود چه یال‌هایی باید اضافه شوند؟

حال برای $k=n-3$، اگر گرافی $k$ همبند باشد، می‌تواند راسی با درجه‌ی کوچک‌تر یا مساوی $k-1$ داشته باشد؟

زمانی که درجه‌ی همه‌ی رئوس بسیار زیاد است (یا تعداد یال‌های گراف بسیار زیاد است) بد نیست نگاهی به مکمل گراف مورد نظر هم انداخته شود.

چون درجه‌ی هر راس از گراف حداقل $n-3$ است، درجه‌ی هر راس در گراف مکمل حداکثر دو است. پس هر مولفه‌ی گراف مکمل به چه صورت است؟

اگر قصد داشته باشیم با بردن تعدادی یال از گراف مکمل به خود گراف، عدد همبندی را به $n-2$ افزایش دهیم، شکل گراف مکمل می‌بایست به چه صورت تغییر کند؟

نشان دهید شرط لازم و کافی $n-2$ همبند بودن، وجود حداقل یک یال در گراف مکمل و تطابق بودن گراف مکمل است.

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

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

اگر مولفه دور باشد،‌ آیا می‌توانید با استفاده از الگوریتمی که برای راهنمایی ۸ ارائه دادید الگوریتمی برای این مولفه ارائه دهید؟