ВсОШ 2023, 11 класс, задача 10

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

Предположим, в графе с вершинами найдётся пара вершин, соединённых ребром, при удалении которых граф не теряет связность; обозначим эти вершины через и . Покрасим оставшиеся вершины таким образом, чтобы число разноцветных рёбер было хотя бы на больше числа одноцветных рёбер — так можно сделать по предположению индукции. Заметим, что вершины и теперь можно покрасить таким образом, что разность между количествами разноцветных и одноцветных рёбер увеличится. В самом деле, без ограничения общности будем считать, что если вершины и не имеют обе чётные степени, то вершина имеет нечётную степень. Тогда покрасим вершину в цвет, который имеет меньшинство её соседей (в случае равенства покрасим в любой цвет), а затем покрасим таким же образом вершину . Очевидно, при каждой покраске требуемая разность не уменьшилась, и хотя бы при одной покраске у соответствующей вершины было нечётное число покрашенных соседей, то есть разность при этой покраске увеличилась. Поскольку до покраски вершин и разность между числом разноцветных рёбер и числом одноцветных рёбер была не меньше , после этой покраски она стала не меньше .

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

В самом деле, рассмотрим произвольное остовное дерево этого графа и подвесим его за любую не висячую вершину. Пусть — наиболее удалённая от корня висячая вершина этого дерева, а — предок этой вершины. Обозначим потомков этого предка через . Заметим, что вершины являются висячими в рассматриваемом остовном дереве. Рассмотрим несколько случаев.

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

Случай 2. Среди вершин есть пара вершин, являющихся висячими в исходном графе. Значит, в исходном графе есть хотя бы две висячие вершины.

Случай 3. Среди вершин есть не больше одной вершины, являющейся висячей в исходном графе. Без ограничения общности, будем считать, что если такая вершина есть, то это вершина . Тогда переподвесим каждую из вершин к любому из её соседей, отличных от : поскольку эти вершины не являются висячими в исходном графе, такой сосед всегда найдётся. После всех переподвешиваний вершины и можно будет удалить из графа, и остовное дерево останется связным — а значит, и сам граф.

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

Замечание. Неравенство из задачи является точным: в частности, в полном графе на вершинах соответствующая разность не может быть строго больше .