ب)

لم1:در مجموعه k مکعب هر عضو k همسایه دارد

لم2:در مجموعه kمکعب دو راس متمایز یا همسایه مشترک ندارند یا دو همسایه مشترک دارند.

دو لم بالا به راحتی قابل اثباتند.

لم 3:اگر راسی را مانندx به زیر مجموعه A بیافزاییم یا بکاهیم،وضعیت تمام رئوس مجاور xتغییر میکند.یعنی اگر yهمسایه x باشد و عضو$F(A)$باشد انگاه عضو Fمجموعه جدید نیست و بالعکس.

لم بالا نیز به راحتی اثبات میشود

با استقرای ضعیف مسئله حل میشود فرض میکنیم حکم برای مجموعه Aدرست باشد وa عضو Aنباشد.

میخواهیم درستی حکم را به ازای مجموعه B که برابر اجتماع دو مجموعه A و {a} است ثابت کنیم.همسایه های راس aرا در نظر میگیریم اگرتعداد همسایه های aکه عضو$ F(A)$ هستند فرد باشد انگا aعضو $F(F(B))$ است برای بقیه رئوس نیز به این روش اثبات میکنیم:

طبق لم 2 هر دو راس یا همسایه مشترک ندارند یا دو همسایه مشترک دارند فرض کنیدb راسی از گراف باشد اگر با a همسایه مشترکی نداشته باشد انگاه با افزودن aتغییری در همسایه های ان به وجود نمی اید پس زوجیت این همسایه ها تغییری نمیکند. حال فرض میکنیم دو همسایه مشترک داشته باشند با بررسی 3 حالت پیش امده در اضافه کردن راس a به این نتیجه میرسیم که زوجیت همسایه هایbکه عضو $F(A)$ هستند با زوجیت همسایه های راس b که عضو $F(B)$ هستند فرقی نمیکند حال که فهمیدیم زوجیت همسایه های راس های گراف Kمکعب که عضو F اند تغییری نکرده نتیجه میگیریم ک هرراس از گراف kمکعب به جزa، اگر قبلا عضو$F(F(A))$ بوده است حال عضو$F(F(B))$ نیز هست و اگر عضو ان نبوده حال نیز نیست

حال ثابت میکنیم تعداد همسایه های راس a که عضو $F(B)$ هستند نمیتواند زوج باشد و برای اثبات ان از برهان خلف استفاده میکنیم.

فرض میکنیم راس a تعداد زوجی همسایه دارد که عضو$F(B)$ هستند حال راس aرا برمیداریم چون قبل از برداشتن راس a تعداد همسایه هایی که عضو$F(B)$ بودند زوج بود حالا طبق لم 3 تعداد همسایه های راس a که عضو $F(B)$ هستند فرد است پس aعضو $F(F(A))$ است که میتوان نتیجه گرفت که $F(F(A)$مساویA نیست که با فرض استقرا در تناقض است چون aعضوA نیست ولی عضو $F(F(A))$هست