#7 Графы II

При подсчёте суммы степеней каждое ребро учитывается ровно два раза: по одному разу у каждого своего конца. Поэтому сумма степеней равна \(2m\).

Сумма степеней равна \(2m\), значит, она чётна. Сумма степеней вершин чётной степени чётна. Поэтому сумма степеней вершин нечётной степени тоже чётна. Сумма нечётных чисел чётна только тогда, когда их количество чётно.

Выберем самый длинный простой путь в дереве. Если у его конечной вершины есть сосед вне пути, путь можно продолжить. Если она соединена с другой вершиной пути, кроме соседней, возникнет цикл. Значит, её степень равна \(1\). То же верно для другого конца пути. Получаем два листа.

В любом связном графе есть остовное дерево. Остовное дерево содержит все \(n\) вершин и имеет ровно \(n-1\) рёбер. Исходный граф содержит все рёбра этого дерева и, возможно, ещё рёбра. Поэтому в нём не меньше \(n-1\) рёбер.

Пусть новое ребро соединяет вершины \(u\) и \(v\). В дереве между \(u\) и \(v\) был ровно один простой путь. Этот путь вместе с новым ребром образует цикл.

Другого цикла быть не может: любой цикл, появившийся после добавления, обязан использовать новое ребро, потому что раньше циклов не было. Тогда оставшаяся часть цикла была бы другим путём между \(u\) и \(v\) в дереве, что невозможно.

Пусть компоненты имеют \(n_1,n_2,\ldots,n_c\) вершин. Каждая компонента — дерево, поэтому в ней \(n_i-1\) рёбер. Всего рёбер

\[\sum_{i=1}^c(n_i-1)=\sum_{i=1}^c n_i-c=n-c.\]

Пусть удаляемое ребро соединяет \(u\) и \(v\). Так как оно лежит на цикле, после удаления этого ребра на оставшейся части цикла всё ещё есть путь из \(u\) в \(v\).

Любой путь в исходном графе, использовавший ребро \(uv\), можно заменить: вместо \(uv\) пройти по этому обходному пути. Значит, связность не нарушается.

Предположим, что в графе есть цикл. Удалим одно ребро этого цикла; связность сохранится. Тогда получим связный граф на \(n\) вершинах с \(n-2\) рёбрами.

Но связный граф на \(n\) вершинах имеет не меньше \(n-1\) рёбер. Противоречие. Значит, циклов нет, и граф является деревом.

Возьмём остовное дерево графа. В нём \(n-1\) рёбер, значит, в исходном графе есть ровно одно ребро сверх остовного дерева. Добавление одного ребра к дереву создаёт ровно один цикл.

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

Пусть граф разбит на доли \(A\) и \(B\), и каждое ребро соединяет вершину из \(A\) с вершиной из \(B\). При движении по циклу вершины по очереди попадают то в \(A\), то в \(B\). После нечётного числа шагов мы оказались бы в другой доле, а для замыкания цикла нужно вернуться в исходную вершину и исходную долю. Значит, длина цикла чётна.

Покрасим вершины с чётным расстоянием от \(v\) в одну долю, а с нечётным — в другую. Нужно доказать, что ребро не соединяет вершины одной доли.

Пусть ребро \(xy\) соединяет две вершины одинаковой чётности расстояний. Возьмём кратчайшие пути от \(v\) к \(x\) и от \(v\) к \(y\). У этих путей есть общий начальный участок; после его удаления остаются два пути одинаковой чётности суммарной длины. Добавив ребро \(xy\), получаем нечётный цикл. Это запрещено. Значит, каждое ребро соединяет разные доли.

Если путь не замкнут, то у каждой промежуточной вершины использованные рёбра разбиваются на пары: вошли и вышли. Поэтому промежуточные вершины имеют чётные степени. Нечётными могут быть только начало и конец пути.

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

Пусть \(x\) — лист, а \(y\) — его единственный сосед. В совершенном паросочетании вершина \(x\) должна быть покрыта каким-то ребром. Единственное ребро, инцидентное \(x\), — это \(xy\). Следовательно, ребро \(xy\) обязательно входит в паросочетание.

Предположим, что существует ребро \(uv\), оба конца которого не являются концами выбранных рёбер. Тогда \(uv\) не пересекается ни с одним ребром паросочетания, поэтому его можно добавить. Это противоречит максимальности по включению.

Значит, каждое ребро имеет хотя бы один конец среди концов выбранных рёбер.

Каждое ребро имеет один конец в \(A\) и один конец в \(B\). Считая рёбра по вершинам доли \(A\), получаем \(d|A|\). Считая по вершинам доли \(B\), получаем \(d|B|\). Это одно и то же число рёбер, значит, \(d|A|=d|B|\). Так как \(d>0\), имеем \(|A|=|B|\).

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

Выберем замкнутый обход с максимальным числом рёбер. Если он использует не все рёбра, то из связности найдётся вершина обхода, из которой выходит неиспользованное ребро в ещё неиспользованную часть. Начиная с неё и двигаясь по неиспользованным рёбрам, снова получим замкнутый обход, который можно вставить в первый. Это увеличит число использованных рёбер, противоречие.

Значит, максимальный обход использует все рёбра.

Пусть \(f\) — число граней. По формуле Эйлера \(n-m+f=2\). Так как граф простой и \(n\ge3\), каждая грань ограничена не менее чем тремя рёбрами. При суммировании длин границ граней каждое ребро считается дважды, значит, \(3f\le2m\).

Тогда \(f\le\frac{2m}{3}\), и \(2=n-m+f\le n-m+\frac{2m}{3}=n-\frac{m}{3}\). Отсюда \(m\le3n-6\).

Необходимость доказана через пары вход-выход: нечётными могут быть только начало и конец незамкнутого эйлерова пути, а у цикла нечётных вершин нет.

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

Если нечётных вершин ровно две, обозначим их \(a\) и \(b\). Добавим новое ребро \(ab\). Теперь все степени стали чётными, поэтому в новом графе есть эйлеров цикл. Удалим из этого цикла добавленное ребро. Оставшаяся последовательность рёбер является эйлеровым путём исходного графа от \(a\) к \(b\).

Пусть \(f\) — число граней. По формуле Эйлера \(n-m+f=2\). В двудольном графе нет нечётных циклов, в частности нет треугольников. Поэтому граница каждой грани имеет длину хотя бы \(4\).

Сумма длин границ граней равна \(2m\), значит, \(4f\le2m\), то есть \(f\le\frac{m}{2}\). Тогда \(2=n-m+f\le n-m+\frac{m}{2}=n-\frac{m}{2}\). Отсюда \(m\le2n-4\).

В дереве нет циклов, значит, нет нечётных циклов. Поэтому дерево двудольно: его вершины можно разбить на две доли \(A\) и \(B\), так что каждое ребро идёт между долями.

Внутри каждой доли рёбер нет, значит, каждая доля является независимым множеством. Из двух чисел \(|A|\) и \(|B|\), сумма которых равна \(n\), одно не меньше \(\lceil n/2\rceil\). Эта большая доля и даёт нужное независимое множество.