همبندی مکمل
نهایی: در ۳ امتحان از ۲۶، روی‌هم ۱ نمره
ایده
در مکمل دو رأس وقتی مجاورند که در مجاور نباشند، پس . رأسی که در با همهٔ رأس‌های دیگر مجاور است در تنهاست و را ناهمبند می‌کند. ولی مکمل هر گراف همبندی ناهمبند نیست: برای رد این ادعا یک گراف همبند بنویس که مکملش هم همبند باشد، مثل .
نمونهٔ نهایی
نهایی خرداد ۱۴۰۳، سؤال ۷، بخش د۰/۵ نمره
با توجه به گراف مقابل به سوالات زیر پاسخ دهید.
د)
آیا گراف همبند است ؟ چرا ؟
درجهٔ رأس را در بشمار؛ با هر شش رأس دیگر مجاور است.
در مکمل، با هیچ رأسی مجاور نیست، یعنی در رأس تنهاست.۰/۲۵ نمره
رأس تنها در گرافی با چند رأس یعنی ناهمبندی؛ پس پاسخ خیر است.۰/۲۵ نمره