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

+Теорема Татта о совершенном паросочетании
+-------------------------------------------
+
+**_В графе G есть совершенное паросочетание $`\Leftrightarrow ∀S \in V(G) o(G-S) ≥ |S|`$_**
+
+Здесь, как _o(G)_ обозначается _количество нечётных компонент связности графа, причём нечётной компонентой называется компонента, в которой нечётное число._ (А чётной компонентой, соответственно будет компонента связности, где чётное количество вершин.)
+
+Доказательство: 
+
+($`\Rightarrow `$)
+Докажем, что если в графе есть совершенное паросочетание выполняется условие: $`\Leftrightarrow ∀S \in V(G) o(G-S) ≥ |S|`$. 
+
+Заметим, что без S граф G разваливается на чётные и нечётные компоненты связности. Нечётные компоненты нельзя покрыть паросочетанием (потому что нечётное число нельзя разбить на пары), а совершенное паросочетание у нас всё таки есть, значит из каждой нечётной компоненты шло хотя бы одно ребро в вершины из S (это ребро мы и брали в паросочетание). Но тогда вершин в S не меньше, чем нечётных компонент связности в G-S. Т.е. $`o(G-S) ≥ |S|`$.
+
+<img src="uploads/c9063e14dbd3267402ab9feb60147c7a/tatt-theorem-1.png"  width="80%" height="80%">
+
+($`\Leftarrow`$)
+Докажем, что если выполняется условие: $`\Leftrightarrow ∀S \in V(G) o(G-S) ≥ |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|`$
+
+<img src="uploads/08c32ab06b1c05107e6008c087fca8b2/tatt-theorem-2.png"  width="100%" height="100%">
+
+Если вершина 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. Такая найдётся, т.к. мы выкинули все вершины, которые соединены со всеми остальными. 
+
+<img src="uploads/a2b8dbeb0cc866c947877847019d8212/tatt-theorem-3.png"  width="50%" height="50%">
+
+Вспомним, что при добавлении $`∀`$ ребра в $`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`$. 
+
+<img src="uploads/619058b50bee0e8759281e4f1dec2e61/tatt-theorem-4.png"  width="50%" height="50%">
+
+Понятно, что наши рёбра zx и yw тоже попали в H. Потому что они были в $`M_1`$ и $`M_2`$ и не могли пропасть, потому что каждое было только в одном паросочетании. Но они могли попасть либо, в один либо в разные циклы. (См картинку) 
+
+<img src="uploads/dca43c9871081e8a8dce33aeb4a4eaf1/tatt-theorem-5.png"  width="100%" height="100%">
+
+1) Если они попали в разные циклы:
+Тогда в каждом цикле возьмём рёбра цвета противоположного zx и yw соответственно. В остальных циклах возьмём любой цвет -- получится совершенное паросочетание в графе $`G^*`$. Противоречие. 
+2) Если они попали в один цикл:
+Противоречие.
+
+В обоих случаях мы получили противоречие => лемма доказана, потому что мы доказывали от противного. 
+
+
+