درخت رو از یه راس غیر برگ ریشه دار می کنیم.

لم) این درخت حداقل یک برگ به رنگ سفید دارد.

اثبات لم: استقرا می‌زنیم، برای n=1,2,3 درخت نهایی و شیوه‌ی رنگ‌آمیزی آن یکتا تعیین شده و حکم برقرار در آنها برقرار است. فرض می‌کنیم اگر $n < k$ حکم برقرار باشد و ثابت می‌کنیم برای $n=k$ نیز لم برقرار است.

برای اثبات از برهان خلف استفاده می‌کنیم، فرض کنید همه‌ی برگ‌ها به رنگ سیاه باشد، مجموعه‌ی همه‌ی برگ‌ها را A و مجموعه‌ی همه‌ی پدر این برگ‌های سیاه را B می‌نامیم. همه‌ی راس‌های A سیاه و راس‌های B سفید هستند. حال چون هر برگ دقیقا یک پدر دارد اما یک پدر می‌تواند پدر چند برگ باشد، پس $|A| \geq |B|$.

اگر همه‌ی این راس‌ها را از درخت حذف کنیم، بازهم تعداد سفید ها از سیاه‌ها در درخت بیشتر خواهند ماند زیرا تعداد راس‌های سیاه حذف شده بزرگتر یا مساوی سفید‌های حذف شده است. پس طبق فرض استقرا یکی از برگ‌های درخت جدید سفید است که این راس به یکی از راس‌های B وصل بوده یعنی دو رنگ سفید به هم وصل بوده اند که این تناقض است. پس فرض خلف باطل و حکم ثابت است.

مسئله‌ی اصلی

همان طور که گفته شد طبق لم یک برگ سفید داریم که آنرا به $v$ نام گذاری می‌کنیم و پدر راس $v$ را با $f$ نام گذاری می‌کنیم. (بدیهی هست که $f$ به رنگ سیاه و تمام فرزندان $f$ به رنگ سفید اند) حال روی تعداد فرزندتان راس $f$ حالت بندی می‌کنیم:

حالت اول: اگر $f$ بیش از یک فرزند داشت. دو حالت داریم، یا یکی از فرزاندنش به غیر از $v$ زیردرختشان (که شامل خوب اون راس هم میشه) درش تعداد سفید ها از سیاه ها بیشتره یا نه. اگه اینجوری بود، مثلا زیر درخت راس y این ویژگی رو داشت، اون زیر درخت رو در نظر میگیریم و طبق فرض استقرا می‌تونیم اونو جوری شماره‌گذاری کنیم که اوکی بشه، اونو شماره گذاری می‌کنیم، عددی که به راس y اختصاص دادیم اگه x بود، به راس v عدد -x رو اختصاص می دیم و بقیه‌ی راس‌های سفید رو ۰ میزاریم. این درسته زیرا حداقل یک غیر صفر در زیر درخت y داریم. همچنین مجموع اعداد راس f برابر با ۰ است. بقیه‌ی راس‌ها اگه در زیر درخت y نباشند، همه‌ی راس‌های مجاورشون ۰ هست پس ۰ هستند.

اگه چنین راسی نبود، پس هر کدوم از زیر درختا تعداد سیاه ها بزرگتر مساوی سفید‌هاست پس کل زیر درخت f تعداد سیاه ها بزرگتر مساوی سفید هاست. کل زیر درخت f رو حذف می‌کنیم، طبق فرض استقرا بقیه رو اوکی می‌کنیم، حالا اگه به پدر f شماره‌ی x رو داده بودیم به راس v شماره‌ی -x رو داده و به بقیه‌ی راس‌ها ۰ می دیم.

حالت دوم: اگه v تنها فرزند f بود. در این صورت با حذف v و f از گراف، دقیقا یک سیاه و یک سفید کم شده، پس درخت باقی مونده شرایط رو داره پس طبق فرض استقرا می‌تونیم درخت باقی مانده رو عدد گذاری معتبر کنیم، حال اگه به پدر راس f عدد x رو دادیم، به راس v عدد -x رو میدیم. بقیه‌ی راس‌ها به غیر از f طبق فرض استقرا اوکی ان و همچنین f نیز اوکیه چون باباش x و بچه‌ش -x عه پس در مجموع مجاوراش ۰ هستند.

پس در هر دو حالت با استفاده از فرض استقرا مسئله حل شد پس گام استقرا ثابت و حکم ثابت شد.