Решение задачи 366

Условие:

В волшебной стране Лариколяндия 100 городов, некоторые из которых соединены авиалиниями. Известно, что из каждого города выходит более 90 авиалиний. Докажите, что найдутся 12 городов, попарно соединенных авиалиниями.

Решение:

Смотрим на задачу, как на граф: города -- вершины, авиалинии -- ребра. Рассмотрим любую вершину. Она не соединена максимум с 8 вершинами. Выкинем вершины, с которыми она не соединена, из графа. Рассмотрим следующую вершину, она также не соединена максимум с 8 вершинами, выкинем их, и так далее. На каждом этапе мы добавляем одну вершину к полному подграфу, а убираем максимум 8. Значит этот процесс закончится не раньше чем через [100/9]=11 операций. В итоге останется полный подграф на 11 вершинах, и еще одна нерассмотренная вершина, которая соединена с каждой из одиннадцати из полного подграфа (иначе бы ее выкинули), значит нашелся полный подграф на 12 вершинах.