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

 Теорема Татта о совершенном паросочетании
 -------------------------------------------
 
-**_В графе G есть совершенное паросочетание $`\Leftrightarrow ∀S \in V(G) o(G-S) ≥ |S|`$_**
+**_В графе $`G`$ есть совершенное паросочетание $`\Leftrightarrow ∀S \in V(G)`$ $`o(G-S) \leq |S|`$_**
 
-Здесь, как _o(G)_ обозначается _количество нечётных компонент связности графа, причём нечётной компонентой называется компонента, в которой нечётное число._ (А чётной компонентой, соответственно будет компонента связности, где чётное количество вершин.)
+Здесь, как $`o(G)`$ обозначается _количество нечётных компонент связности графа, причём нечётной компонентой называется компонента, в которой нечётное число._ (А чётной компонентой, соответственно будет компонента связности, где чётное количество вершин.)
 
 Доказательство: 
 
 ($`\Rightarrow `$)
-Докажем, что если в графе есть совершенное паросочетание выполняется условие: $`∀S \in V(G) o(G-S) ≥ |S|`$. 
 
-Заметим, что без S граф G разваливается на чётные и нечётные компоненты связности. Нечётные компоненты нельзя покрыть паросочетанием (потому что нечётное число нельзя разбить на пары), а совершенное паросочетание у нас всё таки есть, значит из каждой нечётной компоненты шло хотя бы одно ребро в вершины из S (это ребро мы и брали в паросочетание). Но тогда вершин в S не меньше, чем нечётных компонент связности в G-S. Т.е. $`o(G-S) ≥ |S|`$.
+Докажем, что если в графе есть совершенное паросочетание выполняется условие: $`∀S \in V(G)`$ $`o(G-S) \leq |S|`$. 
+
+Заметим, что без $`S`$ граф $`G`$ разваливается на чётные и нечётные компоненты связности. Нечётные компоненты нельзя покрыть паросочетанием (потому что нечётное число нельзя разбить на пары), а совершенное паросочетание у нас всё таки есть, значит из каждой нечётной компоненты шло хотя бы одно ребро в вершины из $`S`$ (это ребро мы и брали в паросочетание). Но тогда вершин в $`S`$ не меньше, чем нечётных компонент связности в $`G-S`$. Т.е. $`o(G-S) \leq |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^*`$ быть тоже не может)
+Докажем, что если выполняется условие: $`\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`$ должно быть чётное число вершин, потому что иначе найдётся нечётная компонента связности и условие Татта для неё не выполнится, ведь если взять $`S = \emptyset`$, тогда $`o(G) ≥ 1`$ (у нас есть минимум одна нечётная компонента). В итоге, получится: $`|S| = 0 < 1 \leq o(G)`$, т.е. будет противоречие. 
 
 Заметим, что добавление рёбер между компонентами в $`G^*`$ не меняет количества нечётных компонент (см картинку). Рёбра внутри компонент нас не особо волнуют. 
 
@@ -28,36 +30,38 @@ $`\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^*)`$
+Если вершина $`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х вершинах, а мы предположили, что таких нет. 
+Будем доказывать от противного. Тогда в графе $`G^* - U`$ есть вершины $`x`$, $`y`$, $`z`$ -- которые образуют галочку  (см картинку). Т.е. в графе есть рёбра $`xy`$, $`yz`$, а $`xz`$ -- нет. Такая галочка найдётся, потому что иначе мы получим треугольник -- это полный граф на 3х вершинах, а мы предположили, что таких нет. 
 
-Пусть есть ещё вершина w. Пусть она не соединена с y. Такая найдётся, т.к. мы выкинули все вершины, которые соединены со всеми остальными. 
+Пусть есть ещё вершина $`w`$. Пусть она не соединена с $`y`$. Такая найдётся, т.к. мы выкинули все вершины, которые соединены со всеми остальными. 
 
 <img src="uploads/a2b8dbeb0cc866c947877847019d8212/tatt-theorem-3.png"  width="30%" height="30%">
 
 Вспомним, что при добавлении $`∀`$ ребра в $`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`$. 
+Тогда пусть $`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`$ и не могли пропасть, потому что каждое было только в одном паросочетании. Но они могли попасть либо, в один либо в разные циклы. (См картинку) 
+Понятно, что наши рёбра $`zx`$ и $`yw`$ тоже попали в $`H`$. Потому что они были в $`M_1`$ и $`M_2`$ и не могли пропасть, потому что каждое было только в одном паросочетании. Но они могли попасть либо, в один либо в разные циклы. (См картинку) 
 
 <img src="uploads/dca43c9871081e8a8dce33aeb4a4eaf1/tatt-theorem-5.png"  width="100%" height="100%">
 
 1) Если они попали в разные циклы:
-Тогда в каждом цикле возьмём рёбра цвета противоположного zx и yw соответственно. В остальных циклах возьмём любой цвет -- получится совершенное паросочетание в графе $`G^*`$. Противоречие. 
+Тогда в каждом цикле возьмём рёбра цвета противоположного $`zx`$ и $`yw`$ соответственно. В остальных циклах возьмём любой цвет -- получится совершенное паросочетание в графе $`G^*`$. Противоречие. 
 2) Если они попали в один цикл:
-Тогда в "ушках", которые обозначены на картинке будет чётное число рёбер, потому что H -- объединение чётных циклов. при этом там будет существовать путь $`P = xCyzCw`$ через весь цикл. А поскольку в этом пути чётное число рёбер можно выбрать паросочетание покрывающее весь этот цикл. В остальных циклах можно выбрать любое из паросочетаний $`M_1`$ и $`M_2`$ и у нас получится совершенное паросочетание на графе $`G^*`$, возникает противоречие.
+Тогда в "ушках", которые обозначены на картинке будет чётное число рёбер, потому что $`H`$ -- объединение чётных циклов. при этом там будет существовать путь $`P = xCyzCw`$ через весь цикл. А поскольку в этом пути чётное число рёбер можно выбрать паросочетание покрывающее весь этот цикл. В остальных циклах можно выбрать любое из паросочетаний $`M_1`$ и $`M_2`$ и у нас получится совершенное паросочетание на графе $`G^*`$, возникает противоречие.
 
 В обоих случаях мы получили противоречие $`\Rightarrow`$ лемма доказана, потому что мы доказывали от противного.
 
@@ -66,4 +70,4 @@ $`M_2`$ -- совершенное паросочетание на $`G^* + yw`$
 <img src="uploads/c21acaf3b41d4dcd3a37b1883b7d4d8b/tatt-theorem-7.png"  width="100%" height="100%">
 
  Из леммы мы получаем, что $`G^* - U`$ -- объединение несвязных полных графов. 
-Эти графы снова могут быть чётными и нечётными компонентами. Нечётных полных графов $`\leq |U|`$ т.к. $`G^*`$ -- чётный. Во всех чётных компонентах можно выделить паросочетание покрывающее все вершины компоненты (потому что компоненты -- полные графы). В нечётных одну не покрытую паросочетанием вершину соединим с U (там все вершины соединены со всеми остальными, и их $`o(G^*-U) \leq |U|`$ значит такое ребро есть и его можно взять в паросочетание). Не покрытые вершины в U можно соединить друг с другом и тоже взять в паросочетание. Значит мы сможем покрыть все вершины паросочетанием и получить совершенное паросочетание. А значит у нас есть противоречие с тем, что мы брали $`G^*`$ -- как надграф G без совершенного паросочетания -- такого графа не существует. Значит и в исходном G есть совершенное паросочетание. Значит теорема доказана. 
+Эти графы снова могут быть чётными и нечётными компонентами. Нечётных полных графов $`\leq |U|`$ т.к. $`G^*`$ -- чётный. Во всех чётных компонентах можно выделить паросочетание покрывающее все вершины компоненты (потому что компоненты -- полные графы). В нечётных одну не покрытую паросочетанием вершину соединим с $`U`$ (там все вершины соединены со всеми остальными, и их $`o(G^*-U) \leq |U|`$ значит такое ребро есть и его можно взять в паросочетание). Не покрытые вершины в $`U`$ можно соединить друг с другом и тоже взять в паросочетание. Значит мы сможем покрыть все вершины паросочетанием и получить совершенное паросочетание. А значит у нас есть противоречие с тем, что мы брали $`G^*`$ -- как надграф $`G`$ без совершенного паросочетания -- такого графа не существует. Значит и в исходном $`G`$ есть совершенное паросочетание. Значит теорема доказана.