به ازای هر رنگ ما تطابق کامل داریم. یعنی میشه رأس ها رو دو به دو به همدیگه متناظر کرد که به هم با اون رنگ وصل باشن. واضحه که هر گراف این شکلی زوج تا رأس داره.

تطابق برا هر رنگ این شکلیه:

به ازای هر n>1 میشه یه یال از رنگ 1 رو حذف کرد که گراف همچنان همبند باشه. چون اگه به دو مؤلفه تبدیل شه با توجه به اینکه بقیه رنگ ها تو هر مؤلفه تطابق کامل دارن باید هر مؤلفه زوج تا رأس داشته باشه ولی باتوجه به اینکه در هرتطابق رنگ 1 باید هر دو رأسش تو یه مؤلفه باشن و دورأسی که یال بین اونا رو جدا کردیم تو دو مؤلفه ی متفاوتن پس هر مؤلفه فرد تا رأس داره. پس به تناقض می رسیم ومی تونیم مطمئن باشیم که با حذف یک یال از رنگ 1 گراف همبنده.

حالا n-1 یال دیگه ی رنگ 1 رو برمی داریم. گراف به یه سری مؤلفه تقسیم میشه. با استقرا رو اون مؤلفه ها میشه از هرکدومشون n-2 یال از رنگ های 2 تا n-2 رو حذف کرد که بازم همبند بمونن.

حالا n-1 یال رنگ 1 رو می ذاریم سر جاشون و گراف مثل قبل همبند میشه و ما 1 یال از رنگ 1 و حداقل 1 یال از رنگ های 2 تا n-2 رو حذف کردیم.

پس حکم ثابت شد.:)

راه حل بدون استقرا

برهان خلف ،اگر با حذف n-1 یال دوبدو ناهمرنگ گراف حاصل ناهمنبد بود در گراف جدید نحوه ای از افراز راس ها به دو بخش A و ‌B خواهیم داشت که بعضی از یال های حذف شده بین این دو بخش بوده اند (حداکثر n - 1 یال ، راستی فرض میکنیم یالی که بین این دو بخشه به رنگ ۱ هست ). و در گراف جدید هیچ یالی بین این دو بخش نیست . (تمام یالهای بینشان همان هایی بودند که حذف شدند)

تمام یال های به رنگ n را در نظر میگیریم ، و میدونیم هیچ کدوم حذف نشده اند.

از اونجایی که تشکیل تطابق میدادن و هر راس دقیقن یک یال به این رنگ داره پس در هر دو بخش A , B زوج راس وجود داره . (چون برای هر بخش ، اگر فقط یال های n رنگی رو در نظر بگیریم ، چیزی که بهوجود میاد یک تطابقه که مسلمن حاوی زوج راسه .)

حالا یال های به رنگ ۱ رو در نظر میگیریم . میدونیم توی بخش A به جز یک راس که یال رنگ ۱ متصل به اون حذف شده ، هریک از باقی رئوس باید دقیقن یک یال رنگ ۱ داشته باشند.

پس 1-|A| راس هستند که اگر در اونها یال های رنگ ۱ رو در نظر بگیریم ، باید تشکیل تطابق کامل بدن (چرا‌؟؟) ولی چون 1-|A| فرده پس امکان تشکیل تطابق نیست و در نتیجه برهان خلفه و ... .