Задача 2.
10 школьников вечером звонили друг другу, никакие два школьника не разговаривали более 1 раза, при этом Ипполит (один из этих 10 школьников) имел разговоров меньше, чем кто-либо другой из этой компании, всего лишь четыре. Докажите, что найдутся 3 школьника, которые попарно разговаривали друг с другом, то есть каждый из них разговаривал с каждым из остальных.
Ответ на Задачу 2.
Рассмотрим граф соответствующий ситуации. В этом графе есть вершина степени 4, а все остальные не меньше 5-ти. Рассмотрим вершину А со степенью не меньше 5-ти. Пусть она соединена с вершинами Б, В, Г, Д, Е (5). Если между какими-то вершинами (5) есть ребро, то нужная тройка есть. Назовем оставшиеся вершины Ж, З, И, К (4). Хотя бы одна вершина из (5) соединена со всеми вершинами из (4), поэтому если между ними есть ребро, то нужная тройка есть. Иначе, посмотрим, где Ипполит. Если он в (4), то все из (5) соединены с (4), и степень Ипполита не менее 5-ти. Если он в (5), то все (4) соединены с (5) и опять, его степень не менее 5-ти.
