در زمان‌های قدیم شایان‌خان نزد سیمرغ می‌رود و از او خوشبختیش را می‌طلبد. سیمرغ هم برای آن‌که ببیند شایان‌خان چند مرده حلاج است به او سوال زیر را می‌دهد!

صورت سوال: گراف $K_n$ که روی هر راس آن یک عدد حقیقی و روی هر یال آن یک لیست سه تایی از اعداد حقیقی مختلف قرار داده شده، به ما داده شده است (لیست قرار داده شده بر روی یال‌های مختلف می‌تواند یکسان یا متفاوت باشد). ثابت کنید که می‌توان از لیست هر کدام از یال‌ها یک عدد را انتخاب کرد که در نهایت رنگ هر دو راس مجاور فرق کند. اگر $w_v$ عدد روی راس $v$ و $l_{uv}$ عدد انتخاب شده برای یال $uv$ باشد آن‌گاه رنگ راس $v$ برابر است با:

$$color(v)=W_v+ \sum_{u \in N(v)} l_{uv}$$

به شایان‌خان کمک کنید تا این سوال را حل کند و به آرزوهایش برسد… ++++ پاسخ | با استقرا روی تعداد رئوس از $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$ هم یکی نیست و اینگونه شایان خان را کمک کردیم :)))))