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

@@ -66,4 +66,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 есть совершенное паросочетание. Значит теорема доказана.