Бат, Великобритания, 2019 год

В социальной сети 2019 пользователей. Некоторые пользователи дружат с некоторыми другими, при этом отношение дружбы взаимно, то есть если пользователь $A$ дружит с пользователем $B$, то $B$ также дружит с $A$. Перестройки следующего типа производится последовательно, по одной перестройке за раз:
   выбираются три пользователя $A,$ $B$ и $C$ таких, что $A$ дружит и с $B$ и с $C$, но $B$ и $C$ не дружат между собой; после чего $B$ и $C$ становятся друзьями, но $A$ теперь не дружит ни с $B,$ ни с $C.$
   Изначально 1010 пользователей имеют по 1009 друзей, а 1009 пользователей имеют по 1010 друзей. Докажите, что существует последовательность перестроек, после которой каждый пользователь будет иметь не более одного друга.

Комментарий/решение

Пусть это граф $G$ с вершинами $A_1,A_2,\ldots, A_{2019}.$ Через $d(X)$ обозначим степень точки $X$.

Поскольку $d(A_i)+d(A_j)\ge 2018,$ любые две вершины имеют общую вершину, значит изначальный граф $G$ связный.

Утверждение 1: Не теряя связанность $G$ можно делать перестройки, пока граф не стал полным или циклом или деревом.

Док-во: Допустим граф не является деревом (иначе утверждение доказано), значит в нем существует цикл. Пусть $G$ свободна от треугольников и возьмем наименьший цикл $C \ge 4$ и $C\neq G $ (если $C=G$, то утверждение доказано). Пусть какая то вершина $X\notin C$ имеет ребро с $Y\in C$, а также $Z\in C$ имеет ребро с $Y.$ Поскольку $G$ свободна от треугольников $Z$ не имеет ребро с $X,$ делаем перестройку для $XYZ$ при этом сохраняется связанность. Если же $G$ имеет треугольник, возьмем наибольший полный граф $C\neq G$ (если $C=G,$ то утверждение доказано) и аналогично определим $X$ и $Y.$ Из за максимальности $C$ в нем существует $Z\in C$ который не имеет ребро с $X,$ тогда проделываем перестройку для $XYZ$. Заметим, что каждый раз количество ребер уменьшается и если мы не получили полный или цикл, то граф в какой то момент перейдет в дерево. Утверждение доказано.

Утверждение 2: Граф перейдет именно в дерево. Для этого достаточно доказать, что граф не сможет перейти в полный или цикл.

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

Значит граф перейдет в дерево и дальше легко получить требуемый граф в условии (рандомно делаем пока можем).