با استقرا روی تعداد رئوس از $n$ به $n+2$ حکم را ثابت می کنیم:
برای n=1,n=4 حکم را خودتان ثابت کنید ;)
فرض کنید حکم برای $n$ برقرار است حکم را برای $n+2$ ثابت می کنیم:
هر حالت انتخاب اعداد روی رئوس را یک رنگ آمیزی می نامیم و در هر رنگ آمیزی به ازای هر دوتایی مرتب از رئوس مانند $u$ و $v$ مقدار $f(u,v)$ را برابر با $color(u)-color(v)$ تعریف می کنیم،حال به ازای تمام رنگ آمیزی های ممکن مقدار ماکسیمم برای $f(u,v)$ را در نظر بگیرید، و یکی از رنگ آمیزی های متناظر با این مقدار ماکسیمم و دو راس متناظر$u$ و $v$ را در نظر بگیرید(بدیهی است در این حالت از تمام یال های متصل به $u$ به جز یال $uv$ مقدار ماکیسممشان از لیست سه تایی و از تمام یال های متصل به $v$ به جز $uv$ مقدار مینیممشان از لیست سه تایی روی این یال ها انتخاب شده اند، در ضمن مقدار انتخاب شده از روی یال $uv$ بر مقدار $f(u,v)$ تاثیری ندارد.)
حال دو راس $u,v$ را در نظر گرفته و از تمام یال های متصل به $u$ به جز یال $uv$ مقدار ماکیسممشان از لیست سه تایی و از تمام یال های متصل به $v$ به جز $uv$ مقدار مینیممشان از لیست سه تایی روی این یال ها انتخاب میکنیم و از یال $uv$ مقدار وسطی از سه مقدار حقیفی روی $uv$ را انتخاب میکنیم،اگر به ازای هر راس به جز $u$ و $v$ مانند $S$ اعداد روی یال های متصل بین $u$ و $v$ و $s$ را به برچسب روی $s$ اضافه کنیم،با توجه به فرض استقرا داریم حکم برای $n-2$ راس دیگر به جز $u,v$ با اعداد جدید روی برچسب هایشان برقرار است بنابراین یک انتخاب برای اعداد روی یال هایشان داریم به طوری که رنگ تمام رئوس به جز $u$ و $v$ با هم متمایز شوند و کافی است در این حالت کافی است ثابت کنیم رنگ $u$ و $v$ از سایر رئوس متمایز است .(بدیهی است رنگ $u$ و $v$ به ازای $n>0$ از هم متمایزند.)
بنا بر تقارن فرض کنید رنگ یک راس مانند $t$ با عدد $u$ یکی باشد داریم در این رنگ آمیزی $f(s,v)=f(u,v)$ از طرفی اگر در همین رنگ آمیزی از برچسب روی $uv$ عدد مینیمم را انتخاب کنیم آنگاه $f(s,v)>f(u,v)$ که متناقض با فرض بیشینه بودن $f(u,v)$ است به طرز مشابه در این رنگ آمیزی رنگ هیج راسی با رنگ $v$ هم یکی نیست و اینگونه شایان خان را کمک کردیم :)))))

• سوال بعد
• سوال قبل