مسابقه شماره 128
در يك مهماني ، هيچ دو نفري كه به تعداد مساوي دوست دارند، هيچ دوست مشتركي نداشته باشند. اگر در اين مهماني حداقل دو نفر با هم دوست باشند، ثابت كنيد فردي وجود دارد كه فقط با يك نفر دوست است.
مسأله به زبان گراف:
فرض كنيد G يك گراف ساده ناتهي باشد به طوريكه
x , y e V d(x)=d(y) => N(x) Ç N(y) = Æ "
ثابت كنيد در اين گراف رأسي با درجه يك وجود دارد