Среди 20 людей есть пары знакомых. Известно, что среди любых пяти людей не более трёх знакомств. Докажите, что можно выбрать10 людей, среди которых нет знакомых.
Подсказка
Если в графе знакомств есть треугольник, то из остальных 17 вершин не выходят ребра. Пусть треугольников нет.
Решение
Если в графе знакомств есть треугольник, то из остальных 17 вершин не выходят ребра. Пусть треугольников нет. Заметим, что каждая компонента связности графа знакомств содержит не более 4 вершин (иначе там есть пять вершин, связанные минимум 4 ребрами). Такие компоненты могут иметь вид одиночного ребра, цепи из двух или трех ребер и «»ежа»» из трех ребер, исходящих из одной вершины. Легко проверить, что в каждой такой компоненте можно отметить не менее половины вершин так, чтобы никакие две отмеченные вершины не были связаны ребром. Сделав это, получим не менее 10 отмеченных вершин, попарно не соединенных между собой.