حکم را برای یک گراف همبند ثابت میکنیم:
مجموع اعداد انتخاب شده روی هر راس و یال های مجاور آن را عدد متناظر با آن راس در نظر بگیرید،در ادامه ابتدا الگوریتمی را برای به دست آوردن ترتیبی از انتخاب اعداد لیست هاارائه می دهیم،سپس ثابت میکنیم با انجام الگوریتم حکم مسئله اثبات می شود و در انتها ثابت می کنیم تعداد مراحل الگوریتم متناهی است .
در ابتدا از هر یک از برچسب ها بزرگترین را انتخاب میکنیم،یکی از رئوسی را که عدد متناظر با آن در بین عدد متناظر با سایر رئوس بیشینه است را در نظر بگیرید و فرض کنید در بخش اول گراف دو بخشی قرار دارد، همچنین $M$ را برابر با عدد متناظر با آن قرار دهید.
حال در مرحله $i$ ام ($i\leq M$)اعمال زیر را انجام میدهیم:
اگر $\[i\equiv m (mod2),1\leq m\leq 2\]$ باشد تمامی رئوسی از گراف را که در بخش $m$ ام قرار دارند و عدد متناظر آنها در این مرحله ( پس از اعمال تغییرات مرحله قبل در صورت وجود) برابر با $\[M-i+1\]$ است را در مجموعه $A_i$ و همجنين تمام رئوسی از بخش دیگر را که بین آنها و مجموعه $A_i$ حداقل یک یال وجود دارد و نیز عدد متناظر آنها برابر با $\[M-i+1\]$ است را در بخش $B_i$ قرار میدهیم.
سپس تمامی رئوسی را که عضو مجموعه $B_i$ هستند و نیز حداقل یک یال به راسی با عدد متناظر کمتر از $\[M-i+1\]$ در این مرحله دارند را در مجموعه $C_i$ و سایر رئوس $B_i$ را در $D_i$ قرار میدهیم و اعضای مجموعه $D_i$ را نقره ای میکنیم.
سپس اعداد انتخاب شده از لیست روی تمام رئوس $D_i$ را به مقدار مینیمم از دو عدد لیستش تغییر میدهیم،همچنین از هر یک از رئوس مجموعه $C_i$ یک یال که به راسی با عدد متناظر کمتر از عدد متناظر این راس متصل است را انتخاب کرده و عدد روی آن یال را از یک به صفر تغییر می دهیم.(به ازای هر i امكان دارد تعدادی از مجموعه های $\[A_{i},B_{i},C_{i},D_{i}\]$ تهی باشند که اشکالی در الگوریتم به وجود نمی آورند.)
حال ثابت میکنیم پس از انجام الگوریتم فوق عدد متناظر هر راس با عدد متناظر تمامی رئوس مجاورش متفاوت است.
با توجه به همبندی گراف بااندکی تامل میتوان دریافت که هر راس $U$ یا به ازای یک $i$ در مجموعه $A_i$ آمده است یا به ازای یک $i$ در مجموعه $D_i$ قرار گرفته است حال برای هر دو حالت حکم را ثابت می کنیم:
1-راس $U$ به ازای یک $i$ در مجموعه $D_i$ قرار گرفته باشد:تمامی یال های خارج شده از راس $U$ به رئوس با عدد متناظر بزرگتر متصل هستند زیرا در مرحله $i$ام راس $U$ یالی به راسی با عدد کمتر از $\[M-i+1\]$ ندارد و از طرفی بعد از انجام عمل این مرحله عدد روی این راس از $\[M-i+1\]$ کمتر خواهد شد.
2-راس $U$ به ازای یک $i$ در مجموعه $A_i$ قرار گرفته باشد: پس از مرحله $i$ام عدد متناظر راس $U$ تغییر نمیکندو همان $\[M-i+1\]$ خواهد ماند از طرفی تمام مجاور های راس $U$ یا یک راس نقره ای هستند که بنا بر 1 نمیتوانند با عدد متناظرشان با عدد متناظر راس $U$ برابر شود یا عضو یک $A_j$ هستند که $j$ باید زوجیتش با $i$ متفاوت باشد و عدد متناظرشان برابر است با $\[M-j+1\]$ که این هم با عدد متناظر راس $U$ متفاوت است.
در ضمن از آنجا که $M$ عددی متناهی است تعداد مراحل متناهی است.
اگر گراف ناهمبند بود ما حکم را برای هر مولفه همبندی ثابت کرده ایم و بنابراین برای گراف کلی نیز حکم را ثابت کرده این زیرا دو مولفه همبندی مجزا راس مجاور ندارند.

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