میگیم که میشه ۱۹۷۹ نفر!
اثبات میکنیم حداکثر ۳ نفر میتونن با همه آشنا نباشن! خب فرض خلف : حداقل ۴ نفر هستن که حداقل یک نفر رو نمیشناسن.

یه گراف در نظر میگیریم که هر کس یه راس داره و راسش به رئوس کسانی که باش آشنا نیستن یال داره. دونفر که سرهای یک یال هستند رو در نظر میگیریم و مینامیم گری و فیل. اگه دو راس فیل و گری و یال هاشون رو از گراف حذف کنیم و یال دیگه ای در گراف باقی بمونه, میتونیم فیل و گری و افراد متناظر با دو سر اون یاله رو انتخاب کنیم بعنوان یک گروه چهار نفره که هیشکی رو نداره که همه رو بشناسه و به تناقض بخوریم.
پس رئوس متناظر این حداقل ۴ نفر که حداقل یک نفر رو نمیشناسن همه در مولفه ی همبندی گری و فیل هستن پس همبند هستند. حالا ۴ نفر رو انتخاب میکنیم که اگه رئوس متناظرشون و یال های بینشون رو برداریم همبند باشن. این گروه چهار نفره بوضوح وجود دارند و باعث تناقض در فرض اولیمونه!

۱۹۷۹ هم راحت قابل رسیدنه اینجوری که ۱۹۷۹ نفر باشن که با همه آشنان و سه نفر دیگه باشن همو نمیشناسن! $^_^$

گراف متمم گراف آشنایی رو در نظر بگیر. براحتی می‌شه دید که تو این گراف دو یال مجزا یا یک راس با درجه‌ی بیشتر از ۲ وجود نداره (چرا؟)

با استفاده از این قضیه هم می‌شه نتیجه گرفت که تو این گراف تعداد راس‌هایی که درجه بیشتر از صفر دارند حداکثر ۳ است. چرا که در غیر اینصورت یکی از شرط‌های بالا نقض می شن.

پس حداکثر سه تا از آدم‌ها هستند که با همه آشنا نیستند.

اگه k نفر داشته باشیم که به همه وصل نیستند اون کی نفر باید به خودشون وصل نباشند اگه
k>=4 باشه چهار نفر پیدا میشند که که هر کدوم به حداقل یکی از خوشون وصل نیستند پس فرض مساله نقض میشه پس k<4