В некотором итальянском городе ведут свои тёмные делишки 20 мафиозных кланов, причём
известно, что каждый клан враждует хотя бы с 14 другими. Всегда ли найдутся 4 клана, попарно
враждующие друг с другом?

Предыдущий
вопрос Следующий
вопрос

Для того, чтобы найти ответ на этот вопрос, мы можем воспользоваться графовой моделью, где вершины представляют мафиозные кланы, а рёбра - враждебные отношения между ними.

Из условия известно, что каждый клан враждует хотя бы с 14 другими. Это значит, что степень каждой вершины в графе как минимум 14. Попробуем применить теорему о рукопожатиях в графах: сумма степеней всех вершин в графе равна удвоенному числу рёбер.

Предположим, что существуют 4 клана, попарно враждующие друг с другом. Тогда рёбер в этом подграфе будет 6 (4+3+2+1). Сумма степеней вершин в подграфе будет как минимум 56 (4*14). Это противоречит условию, что сумма степеней всех вершин должно быть равно удвоенному числу рёбер (6).

Следовательно, всегда найдутся 4 клана, попарно не враждующие друг с другом.