در گرافی n راسی درجه ی هیچ راسی بیشتر از ۵ نیست.ثابت کنید میتوان راسهای این گراف را با ۳ رنگ طوری رنگ کرد که تعداد یالهایی که دو سرشان همرنگ اند حداکثر n/2 باشد.
یه گرافی که بهمون میدن(گراف ساده) که درجه ی هر راسش حداکثر ۵ هست.طبیعتا یالها هم دادن بهمون دیگه!!.بعد ما میایم هر کدوم از راسها رو با یکی از ۳ رنگ داده شده رنگ می کنیم.بعد اونا میان گراف رو بررسی میکنن و تعداد یالهایی که دو سرشون همرنگه رو میشمرن.میخوایم ثابت کنیم ما میتونیم طوری رنگ کنیم که
2016-01-24 20:09:41 -0600 کنکوریوقتی اونا شمردن , تعدادش حداکثر نصف تعداد راس ها بشه.امیدوارم خوب توضیح داده باشم.:)
2016-01-24 20:10:47 -0600 کنکوریبدیهی است که کلیه راسها را میتوان به ۶ دسته افراز کرد به طوری که هیچ دو راسی در یک دسته همسایه نباشند.
حال سه دسته با تعداد اعضای بیشتر را در نظر میگیریم و اعضای هر دسته را به صورت یکسان و متفاوت با دسته دیگر رنگ می کنیم.
حال به سراغ سه دسته دیگر می رویم (میدانیم مجموع اعضای این سه دسته کوچکتر مساوی n/2 می باشد)
به ازای هر کدام از اعضای این مجموعه ها بدیهی است که یکی از یه مجموعه ی اولیه است که حداکثر یک راس همسایه با ان دارد.پس این عضو را در ان می اندازیم و با تکرار این کار حکم ثابت می شود.