Как решить эту задачу на графы?? Заранее спасибо В группе 49 человек. Мы знаем, что если 3 человека попарно незнакомы друг с другом, то какие-то двое из них имеют в группе общего знакомого. Докажите, что кто-то из людей имеет в группе хотя бы 6 знакомых.

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

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

Построим граф, в котором нет трех людей, попарно незнакомых друг с другом. Такой граф может быть построен следующим образом: обозначим трех человек вершинами A, B, C и проведем между ними ребра. Пусть каждый из них имеет по 22 знакомых. Давайте добавим к ним еще одного человека и соединим его с каждым из предыдущих трех. Таким образом, у нового человека будет 6 знакомых. Полученный граф удовлетворяет условиям задачи.

Таким образом, мы доказали, что в группе из 49 человек, если нет трех человек, попарно незнакомых друг с другом, то кто-то из людей обязательно имеет хотя бы 6 знакомых.