В компании 62 человека. Каждый из них знаком не менее, чем с тремя из этой компании. Известно, что у любых двух знакомых есть по крайней мере один общий знакомый. Также известно, что в компании нет четвёрки, в которой любые двое знакомы друг с другом.

Добавлена: 26.09.2026
Обновлена: 26.09.2026
Предмет: Логика
Автор: Кэмп

#Математическая логика
#Теория множеств

Условие:

В компании 62 человека. Каждый из них знаком не менее, чем с тремя из этой компании. Известно, что у любых двух знакомых есть по крайней мере один общий знакомый. Также известно, что в компании нет четвёрки, в которой любые двое знакомы друг с другом. Любые двое знакомых пожали друг другу руки.

Решение:

Дано

Количество человек в компании: $n = 62$ .
Степень каждой вершины (количество знакомых у каждого человека): $d(v) \ge 3$ для любого $v$ .
Если вершины $u$ и $v$ соединены ребром (знакомы), то у них есть общий сосед (существует вершина $w$ , такая что $u \sim w$ и $v \sim w$ ).
В графе нет клики размера 4 (отсутствует $K_4$ — подграф из 4 вершин, где все соединены со всеми).
Количество рукопожатий равно количеству ребер в графе $|E|$ .