Теорема Татта о совершенном паросочетании

В графе G есть совершенное паросочетание \Leftrightarrow ∀S \in V(G) o(G-S) \leq |S|

Здесь, как o(G) обозначается количество нечётных компонент связности графа, причём нечётной компонентой называется компонента, в которой нечётное число. (А чётной компонентой, соответственно будет компонента связности, где чётное количество вершин.)

Доказательство:

(\Rightarrow )

Докажем, что если в графе есть совершенное паросочетание выполняется условие: ∀S \in V(G) o(G-S) \leq |S|.

Заметим, что без S граф G разваливается на чётные и нечётные компоненты связности. Нечётные компоненты нельзя покрыть паросочетанием (потому что нечётное число нельзя разбить на пары), а совершенное паросочетание у нас всё таки есть, значит из каждой нечётной компоненты шло хотя бы одно ребро в вершины из S (это ребро мы и брали в паросочетание). Но тогда вершин в S не меньше, чем нечётных компонент связности в G-S. Т.е. o(G-S) \leq |S|.

(\Leftarrow)

Докажем, что если выполняется условие: \Leftrightarrow ∀S \in V(G) o(G-S) \leq |S|, в в графе есть совершенное паросочетание.

Предположим что в графе G выполняется условие, но совершенного паросочетания нет. Построим надграф G - G^* такой, что при добавлении любого ребра в G^* появится совершенное паросочетание. (НО в G^* совершенного паросочетания нет! Т.е. полным G^* быть тоже не может)

Понятно, что в G должно быть чётное число вершин, потому что иначе найдётся нечётная компонента связности и условие Татта для неё не выполнится, ведь если взять S = \emptyset, тогда o(G) ≥ 1 (у нас есть минимум одна нечётная компонента). В итоге, получится: |S| = 0 < 1 \leq o(G), т.е. будет противоречие.

Заметим, что добавление рёбер между компонентами в G^* не меняет количества нечётных компонент (см картинку). Рёбра внутри компонент нас не особо волнуют.

\Rightarrow o(G^* - S) \leq o(G-S) \leq |S|

Если вершина v соединена со всеми остальными вершинами, её степень d_G(v) = v(G) - 1. Поскольку G^* -- не полный, то множество U вершин соседних со всеми остальными не совпадает с V(G). |U| \neq v(G^*)

Докажем лемму -- (G^* - U -- объединение полных графов не связанных между собой)

Будем доказывать от противного. Тогда в графе G^* - U есть вершины x, y, z -- которые образуют галочку (см картинку). Т.е. в графе есть рёбра xy, yz, а xz -- нет. Такая галочка найдётся, потому что иначе мы получим треугольник -- это полный граф на 3х вершинах, а мы предположили, что таких нет.

Пусть есть ещё вершина w. Пусть она не соединена с y. Такая найдётся, т.к. мы выкинули все вершины, которые соединены со всеми остальными.

Вспомним, что при добавлении ∀ ребра в G^* появляется совершенное паросочетание. Пусть тогда:

M_1 -- совершенное паросочетание на G^* + xz

M_2 -- совершенное паросочетание на G^* + yw

Т.к. до добавления этих рёбер совершенных паросочетаний не было -- добавленные рёбра входят в соответствующие паросочетания. xz \in M_1, yw \in M_2

Тогда пусть H -- объединение M_1 и M_2. Т.е. H = M_1 \Delta M_2. Т.к. M_1 и M_2 -- совершенные паросочетания H -- объединение чётных циклов, в которых чередуются рёбра из M_1 и M_2.

Понятно, что наши рёбра zx и yw тоже попали в H. Потому что они были в M_1 и M_2 и не могли пропасть, потому что каждое было только в одном паросочетании. Но они могли попасть либо, в один либо в разные циклы. (См картинку)

Если они попали в разные циклы: Тогда в каждом цикле возьмём рёбра цвета противоположного zx и yw соответственно. В остальных циклах возьмём любой цвет -- получится совершенное паросочетание в графе G^*. Противоречие.
Если они попали в один цикл: Тогда в "ушках", которые обозначены на картинке будет чётное число рёбер, потому что H -- объединение чётных циклов. при этом там будет существовать путь P = xCyzCw через весь цикл. А поскольку в этом пути чётное число рёбер можно выбрать паросочетание покрывающее весь этот цикл. В остальных циклах можно выбрать любое из паросочетаний M_1 и M_2 и у нас получится совершенное паросочетание на графе G^*, возникает противоречие.

В обоих случаях мы получили противоречие \Rightarrow лемма доказана, потому что мы доказывали от противного.

Продолжим доказательство теоремы Татта:

Из леммы мы получаем, что G^* - U -- объединение несвязных полных графов. Эти графы снова могут быть чётными и нечётными компонентами. Нечётных полных графов \leq |U| т.к. G^* -- чётный. Во всех чётных компонентах можно выделить паросочетание покрывающее все вершины компоненты (потому что компоненты -- полные графы). В нечётных одну не покрытую паросочетанием вершину соединим с U (там все вершины соединены со всеми остальными, и их o(G^*-U) \leq |U| значит такое ребро есть и его можно взять в паросочетание). Не покрытые вершины в U можно соединить друг с другом и тоже взять в паросочетание. Значит мы сможем покрыть все вершины паросочетанием и получить совершенное паросочетание. А значит у нас есть противоречие с тем, что мы брали G^* -- как надграф G без совершенного паросочетания -- такого графа не существует. Значит и в исходном G есть совершенное паросочетание. Значит теорема доказана.