روی تعداد اعضای یعنی کل دختر ها پس ها استقراء قوی می زنیم
k=1 خیلی بدیهی است !
k=1,2,3,4,...n فرض می کنیم درست باشه
k=n+1 ؟ : حکم

با توجه به شکل:
حالا یه دختری رو می گیریم که با ماکسیمم پسر ها دوست باشه
حالا با توجه به فرض استقرا مجموعه در C می توان زیرمجموعه ای مانند 'C انتخاب کرد که شامل بیش از نیمی از دانش آموزان باشه و همه پسر ها با تعداد فردی از دختر ها دوست باشد پس با توجه به فرض C'>C/2

با توجه به شکل : مجموعه S را نیز دوباره به دو مجموعه افراز می کنیم :D1 , D2
حال اگر D1>D2
تمام اعضای D1 و دختر A را و تمام اعضای 'C میگیریم در غیر اینصورت
تمام اعضای D2 و اعضای 'C را می گیریم
که در هر دو حالت تعداد اعضای مجموعه از n/2 بیشتر است و در فرض صدق می کند .

بعضيا سر اين جواب مشكل داشتن و متوجه نمي شدند من دوباره توضيح مي دم با اجازه ي كلم برگ عزيز :

استقرا روي تعداد دخترا. ببينيد پايه ي استقرا كه اوكيه. حالا فرض كنيد براي 2 تا k-1 اوكي باشه. حالا ما براي k اثبات مي كنيم.تعداد اعضاي كل كلاس رو b بگيريد. يك دختر با دوستاش مي ياريم بيرون (اهميتي نداره چند تا دوست داشته باشه منظور از دوستاش پسران) بعد اين مجموعه را A مي ناميم. كه تعداد a نفر داره. حالا b-a نفر باقي مي مونه طبق فرض داريم b-a چون از k كوچكتر هست پس b-a)/2) تعداد اعضاي يك مجموعه از افراد كلاس هست كه پسرا با تعداد فردي از دخترا دوستند و نام اون رو C مي زاريم. حالا از بين a نفر باقي مونده اونايي كه با تعداد فردي از مجموعه ي C دوستن را T مي ناميم. از طرف ديگه اون هايي كه با تعداد زوجي از C دوستند رو (به علاوه ي دختري كه بينشونه ) R مي گيريم. خوب حالا يكي از R و T حتما بزرگتر مساوي a/2 هست (مي شه بگيم از لانه كبوتري نتيجه مي گيريم اما كاملا واضحه). اگه T با C جمع بشه چون تمام پسر ها دوست فرد دارند و اشتراكي هم بين دو مجموعه نيست مجموعه ي نهايي پسر ها داراي تعداد فردي دوست دختر هستند پس اوكي مي شه. اگه بگيم R با C جمع بشه چون پسر هاي R علاوه بر تعداد زوجي كه از C دوست دختر دارند يكي هم از مجموعه ي A دارند پس فرد مي شه و چون دو مجموعه اشتراكي ندارند باز هم اوكي مي شه. حال گفتيم كه يكي حداقل a/2 هست (يا R يا T) پس اون يكي وقتي با C جمع بشه حكم اثبات مي شه.