رنگ آمیزی گراف کامل با ۳ رنگ

[mahanmath]

یه سوال بامزه :


یال‌های گرافی‌ کامل را طوری با ۳ رنگ رنگ آمیزی کردیم که هیچ مثلث رنگارنگی نداریم , یعنی‌ هر ۳ رنگ روی یال‌های اون مثلث اومده باشند. ثابت کنید زیر گراف القایی روی حداقل یکی‌ از رنگ‌ها ناهمبند خواهد بود .

 

[erfan_ashorion]

پاسخ : رنگ آمیزی گراف کامل با ۳ رنگ

سوالش قشنگ بود آقا ماهان ممنون:67:
احتمالا قصد نوشتن جوااب نیست وگرنه خود استاد مینوشتن ولی خو من یه راهنمایی مینویسم!
یه استقرا بزنید رو تعداد رئوس!حالا یه راس رو حذف کنید به برهان خلف فرض میکنیم که بتونیم این کارو بکنیم!حالا وقتی این راسو حذف میکنیم راس های باقیمونده طبق استقرا رو یه رنگ همبند نیستند حالا اون راس رو اضافه کنید یه سری مجموعه همبندی داریم از فرض استقرا که بینشون هیچ یالی از رنگی خاص مثلا یک نیست!حالا ثابت کنید که باز هم نمیتونیم این کارو بکنیم!استاد اگه اجازه بدن جوابشو میزارم بقیشو:d

 

[mahanmath]

پاسخ : رنگ آمیزی گراف کامل با ۳ رنگ

مرسی‌ :67:،نمیخواد باقیشو بنویسی‌ . همین که استقرا بزنیم روی تعداد راس‌ها مساله بدیهی‌ می‌شه .

 

[hoco.hc]

پاسخ : رنگ آمیزی گراف کامل با ۳ رنگ

بافی نداره دیگه, همون استقرا و در نظر گرفتن ساختار یکی از رنگ ها