سلام

دو قسمت می کنیم اینکه برای مقادیر کوچکتر مساوی دو به توان k می شه ساخت و قسمت دوم اینکه برای مقادیر بزرکتر از n نمی شه

قسمت اول:

با استقرا روی k حکم رو ثابت می کنیم

پایه: k = 1 الالن n یا صفره یا 1 که در هر صورت با اجتماع یک گراف دو بخشی می شه اونو ساخت

گام: n رو به دو قسمت کف n / 2 و سقف n / 2 تقسیم می کنیم هر دو از دو به توان k - 1 کوچکتر اند پس می شه هر کدوم رو به صورت اجتماع k - 1 گراف دو بخشی در نظر گرفت هر کدوم از گراف های دو قسمت رو دو به دو با هم در نظر می گیریم

الان فط یال های بین دو قسمت مونده که اون ها گراف k رو می سازن که دو بخشیه

قسمت دوم:

با اصل اکسترمال حکم رو ثابت می کنیم

کوچکترین مقداری رو که n > 2^k و گراف n راسی رو می شه به صورت اجتماع k گراف دو بخشی ساخت در نظر بگیرید یکی از اون k گراف رو در نظر بگیرید. یکی از بخشهای اون بیشتر از n / 2 راس داره اون رو در نظر بگیرید. اگه m تا راس باشن خواهیم داشت:

(m > (n / 2

و یال های بین اون ها رو به صورت اجتماع k - 1 گراف دو بخشی هستن پس:

(m > 2 ^ (k -1

n > m

ولی طبق فرض n کوچکترین عدد بود.

برای هر راس یه شماره از ۱ تا n در نظر بگیر (‌ باینری شماره)
بعد k تا دوبخشی اینجوری میسازیم
در دوبخشی i رقم i ام شماره هر فرد و در نظر میگیریم اگه ۰ بود دسته ۱ اگه ۱ بود دسته ۲ میذاریم
چون رقم هر دو فرد حداقل در یک بیت متفاوت هر دو راسی حداقل یک بار در دو دسته متفاوت امده اند
پ.ن : با استقرا هم راحت حل میشه