Считаем рёбра

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

Первое решение. Докажем, что из какой-то вершины по прежнему выходит хотя бы рёбер. Если из каждой вершины выходит не более рёбер, то всего рёбер не более, чем

Тогда возьмём вершину наибольшей степени (её степень не менее ), назовём её и рассмотрим всех знакомных этого человека. Если бы они все рассорились, из графа удалилось бы не менее ребер. Таким образом, у найдутся знакомых, которые по прежнему дружат, и вместе с они образуют компанию из трёх друзей.

Второе решение. Cначала докажем лемму.

Лемма. Если в графе на вершинах нет треугольников, то в нём не более рёбер. Докажем это.

Рассмотрим вершину наибольшей степени (пусть ). Пусть вершина cоединена с Ясно, что никакие и не могут быть соединены, потому что иначе в графе будет треугольник Степень оставшихся вершин не превосходит Таким образом, всего в графе не более Лемма доказана.

Давайте предположим, что в полученном графе нет треугольников. Тогда по лемме в графе не более рёбер, но их Пришли к противоречию.