Регион 2023

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

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

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

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

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

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

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

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