Задача 100

от

В графе 80 вершин и 20 ребер. Разрешается взять любую вершину, стереть все выходящие из нее ребра и соединить ее со всеми вершинами, с которыми она была не соединена. Докажите, что такими операциями можно получить граф, в котором не менее 900 треугольников.

Подсказка

Пусть K — множество концов этих 20 ребер, и |K|=k. Предположим, что k \leq 35. Тогда рассмотрим 80-k \geq 45 остальных вершин и применим к каждой из них операцию, описанную в условии задачи (порядок операций не имеет значения).

Решение

Пусть K — множество концов этих 20 ребер, и |K|=k. Предположим, что k \leq 35. Тогда рассмотрим 80-k \geq 45 остальных вершин и применим к каждой из них операцию, описанную в условии задачи (порядок операций не имеет значения). В результате нетрудно понять, что для каждого из наших 20 ребер появится 80-k треугольников с этим ребром (и каждой из не входящих в K вершин). Итого мы имеем 20(80-k) \geq 20 \cdot 45=900 треугольников.

Пусть k \geq 36. Всего у 20 ребер 40 концов и легко понять, что есть не менее 12 ребер, концы которых не совпадают с другими концами наших 20 ребер. Выберем 5 таких ребер — пусть это ребра a_{1} b_{1}, \ldots, a_{5} b_{5}. Обозначим через S множество, состоящие из вершин a_{1}, \ldots, a_{5}, b 1, \ldots b 5 и произвольных 40 вершин не входящих в K. Применим операцию ко всем 50 вершинам множества S. Тогда на каждом из ребер a_{1} b_{1}, \ldots, a_{5} b_{5} образуется по 30 треугольников (со всеми вершинами, не входящими в S ), а на каждом из 15 оставшихся ребер — по 50 треугольников (со всеми вершинами множества S ). Итого получается 5 \cdot 30+15 \cdot 50=150+750=900 треугольников.