گراف با مرتبه و اندازه مشخص و حداکثر تعداد رأس ها با یک درجه مشخص

Question

یک گراف با 12 رأس و 16 یال حداکثر میتواند چند رأس درجه 3 داشته باشد؟

پاسخ نامه کتاب میگوید 9 تا ولی من راه حل آن را نمیفهمم راستش من یک گراف با همین شرایط ولی با ۱۰ راس درجه ۳ کشیدم . میخواستم ببینم یک وقت راه حلم غلط نباشه

Answer 1

پاسخ عدد ۱۰ است. نخست توجه کنید که بیشتر از ۱۰ ممکن نیست. دلیل آن هم به فرمول «جمع درجهٔ گره‌ها برابر با دوبرابر تعداد یال‌ها می‌شود» است. اگر ۱۱ یال از این گراف درجهٔ ۳ داشته باشند آنگاه جمع درجه‌های گراف برابر با ۳۳ بعلاوهٔ یک عدد مثبت دیگر است که این عدد (درجهٔ گرهٔ دوازدهم) هر چه باشد نتیجهٔ نهایی اکیدا بزرگتر از $2\times 16=32$ می‌شود.

اکنون به سراغ ساخت حداقل یک گراف با ۱۲ گره که ۱۰ تای آنها درجهٔ ۳ هستند و با ۱۶ یال بسازیم. جمع دو گرهٔ آخر باید برابر با $(2\times 16)-(10\times 3)=2$ شود. چون درجهٔ یک گراف یک عدد طبیعی (صحیح مثبت) است و تنها دو عدد طبیعی که جمعشان دو شود ۱ و ۱ است پس این دو گره اجبارا باید از درجهٔ یک باشند. یک حالتِ ممکن این است که این دو گره به هم متصل و یک یالِ منزوی باشند (پس گراف ناهمبند داریم). تضمینی تا اینجا نیست که حتما این اتفاق بیفتد ولی به هر حال بیاییم این حالت را امتحان کنیم. اکنون باید یک گراف با۱۰ گره درجهٔ ۳ و $16-1=15$ یال پیدا کنیم. چون تعداد گره‌ها زوج است اگر آنها را دایره‌وار بچینیم و هر گره را به گرهٔ پسینش وصل کنیم و قطرهای این ۱۰-ضلعی را هم اضافه کنیم یک گراف با گره‌های فقط از درجهٔ ۳ خواهیم داشت. اما تعداد یال‌ها چقدر است؟ برابر با تعداد گره‌ها بعلاوهٔ نصف تعداد گره‌ها (که تعداد قطرهاست) می‌شود یعنی ۱۵. پس مأموریت تکمیل شد. این نتیجه می‌دهد که عدد ۱۰ یک کران بالای دقیق است و اتخاذ می‌شود. برای شکل می‌توانید به شکل‌های زیر نگاه کنید که بوسیلهٔ نرم‌افزار Maple ترسیم کردم (البته رسم آنها با دست زمانی نمی‌برد). برای کسانی که گراف دوبخشی می‌دانند، نمایشِ دوبخشی این گراف را نیز گذاشته‌ام.