g : کمر گراف = کوتاه ترین دور در گراف

اولا ساده سازی مساله بدین صورت است که گراف کمتر از ۱۰ بخشی نمیتواند باشد . یعنی عدد رنگی گراف $\chi(G) = 10$ است .

ثانیا شهود تقریبی ما از گراف میگوید که وقتی عدد رنگی ۱۰ است یعنی احتمالا تعداد یال ها خیلی زیاد هستند . پس درجه ها هم زیاد هستند . کمی با کمر گراف و راس با کمترین درجه کار میکنیم . چون مساله ی عدد رنگی به دلتای کوچک $\delta$ خیلی مربوط است . مستقیما بخش ب را ثابت میکنیم .

برهان خلف :

$g>5$ هر راس از بیرون g حداکثر به یکی از g یال دارد (در غیر اینصورت دور کمتری ساخته میشود و با کمترین دور بودن g در تناقض است. میتوانید این را بررسی کنید)پس حداکثر ۲۴ راس باقیمانده هر کدام یک یال به g دارند(میتواند هر کدام از راس ها باشد ولی در مجموع حداکثر یک یال دارند) . طبق اصل لانه ی کبوتری در بیشترین حالت، حداقل یک راس از حداقل ۶راس g وجود دارد که حداکثر از بیرون g $\lfloor \frac{24}{6} \rfloor $ یال به آن وارد شده یعنی ۴ تا . دو تا یال هم که آن راس درون g دارد(یال های دور) . پس میدانیم $\delta \le 2 + 4 = 6 $ است. حالا میدانیم وقتی دلتا کوچک کمتر مساوی ۶ است یعنی به راحتی میتوانیم با ۷ رنگ گراف را رنگ کنیم . برای اینکار استقرا میزنیم و دلتای کوچک را حذف میکنیم .

به طور فرمال تر مینویسیم :

فرض استقرا : برای $ g \ge 6,n\le3۰$ نتیجه میدهد که $\chi\le 7$

اگر این را اثبات کنیم با برهان خلف ما در تناقض است و مساله اثبات میشود .

پایه استقرا : برای گراف بدون دور یا همان جنگل($g=\infty$) واضح است که دو رنگ کافی است.

گام استقرا : راس $\delta$ را حذف میکنیم . n کمتر اکید میشود . و g هم بزرگتر مساوی میشود . در برگشت راس دلتا هم چون طبق گفته های بالا حداکثر دلتا ۶ است و ما داریم $\chi \le 7$ پس در بدترین حالت تمام ۶ همسایه ی دلتا رنگ های مختلفی دارند اما ما رنگ هفتم در فرض استقرا داریم و میتوانیم دلتا را با رنگ هفتم رنگ کنیم . یا به اصطلاح دلتا یک رنگ آزاد دارد که به آن اختصاص میدهیم . پس از طرفی مساله میگوید $\chi = 10$ و ما از طرفی اثبات کردیم که $\chi \le 7$ پس از تناقض حاصله حکم مساله اثبات شد.

با همین راه میتوانید حتی اثبات کنید که $g \le 4$ و با یک راه دیگر میتوان اثبات کرد حتی کمتر مساوی ۳!!!