Задача
COM-B1-M11-P021 Трое знакомых
#21
★★★★☆ Уровень 4 из 5
В компании \(10\) человек каждый знаком не менее чем с \(6\) другими. Докажите, что найдутся трое попарно знакомых.
Возьмите одного человека и посмотрите на его знакомых.
Пусть \(A\) - любой человек. У него есть как минимум \(6\) знакомых. Если среди этих знакомых есть знакомая пара, то вместе с \(A\) получаем тройку. Если знакомых пар среди них нет, то каждый из этих \(6\) людей знаком с \(A\) и может быть знаком только с тремя людьми вне этой шестерки и вне \(A\), значит его степень не больше \(4\). Это противоречит условию степени не меньше \(6\).
Экстремальный графовый аргумент.