Изменения

|statement= <tex>(n + |S| + odd(G \setminus S)) \; mod \; 2 = 0 \; </tex>, где <tex>G</tex> {{- --}} граф с <tex>n</tex> вершинами, <tex>S \in {V}_{G}</tex>

<tex>|S|\; + \; \sum_{i=1}^{k}k_i \; = \; n \; </tex>, т. к. так как в сумме это все вершины исходного графа <tex>G</tex>. Возьмем данное равенство по модулю два: <tex>(|S|\; mod\; 2 \; + \; \sum_{i=1}^{k}(k_i \; mod \; 2)) \; mod \; 2 = \equiv \; n \; (mod \; 2)</tex>В сумме <tex>\sum_{i=1}^{k}(k_i \; mod \; 2)</tex> число единиц равно числу нечетных компонент <tex>odd(G \setminus S)</tex>. Таким образом, <tex> \forall S \in V : \; (odd(G \setminus S) + |S|) \; mod \; 2 \; = \equiv \; n \; (mod \; 2 ) \;</tex>.

<tex> \forall S \in V : \; (odd(G \setminus S) + |S|) \; mod \; 2 = \; \equiv \; n (\; mod \; 2) \;</tex>

1) . Если <tex> \max\limits_{S \in V}(odd(G \setminus S) \; - \; |S|) \; = 0 \; </tex>, тогда для любых <tex>\forall \; S \in V: \; odd(G \setminus S) \leq |S| \; </tex> и выполнен , следовательно выполнено условие [[Теорема Татта о существовании полного паросочетания|критерий теоремы Татта]], значит в графе есть совершенное паросочетание, т.е. то есть его дефицит равен нулю.  2) Если <tex> \max\limits_{S \in V}(odd(G \setminus S) - |S|) = k \; </tex>, тогда рассмотрим исходный граф <tex>G</tex> и полный граф <tex>K_k</tex> с <tex>k</tex> вершинами, множество вершин нового графа обозначим как <tex>W</tex>. Каждую вершину вспомогательного графа соединим с каждой вершиной <tex>G</tex>. Получим новый граф <tex>H \; = \; K_k + G \;</tex>, докажем, что для него выполнено условие Татта. Докажем, что <tex>\forall S \in V_{H}: odd(G \setminus S) \; \leq \; |S| \; </tex>. Рассмотрим <tex>S \; \subset \; V_H\;</tex>.

2. Если <tex>W \notmax\subset limits_{S \in V}(odd(G \setminus S) - |S|) = k \; </tex>, тогда поскольку рассмотрим исходный граф <tex>K_kG</tex> и полный и все его вершины связаны с каждой вершиной графа <tex>G</tex>, то граф <tex>HK_k</tex> связный и с <tex>odd(H \setminus S) \; = \; 0 \;k</tex> или вершинами, множество вершин нового графа обозначим как <tex>odd(G \setminus S) \; = \; 1 \;W</tex>. В случае Каждую вершину <tex>odd(H \setminus S) \; = \; 0 \; K_k</tex> условие очевидно выполняется т.к соединим с каждой вершиной <tex>\forall S \in G : 0 \; \leq \; |S| \;</tex>. Рассмотрим случай Получим граф <tex>odd(H \setminus S) \; = \; 1 \;</tex>, <tex>|V_H| \; = \; n \; + \; k \; = \; n \; K_k + \; odd(G \setminus A) \; - \; |A| \; </tex>, где докажем, что для него выполнено условие теоремы Татта. Докажем, что для любых <tex>A \; = \; arg \max\limits_{S \in VV_{H}(: odd(H \setminus S) \; - \leq \; |S|) \; </tex>. Разность Рассмотрим <tex>odd(G \setminus A) S \; - \; |A| subset \; </tex> имеет ту же четность, что и <tex>n</tex>, поэтому <tex>|V_H|</tex> четно, значит, по лемме, мощность <tex>S</tex> нечетна, следовательно она не равна нулю, значит <tex> 1 \leq |S| ;</tex>.:

* Если <tex>W \not\subset S \;</tex>, тогда поскольку граф <tex>K_k</tex> полный и все его вершины связаны с каждой вершиной графа <tex>G</tex>, то граф <tex>H</tex> связный и <tex>odd(H \setminus S) \; = \; 0 \;</tex> или <tex>odd(G \setminus S) \; = \; 1 \;</tex>. ** В случае <tex>odd(H \setminus S) \; = \; 0 \; </tex> условие очевидно выполняется, так как для любых <tex>S \cap V)) in G : 0 \; \leq \; |S | \cap V;</tex>. ** Рассмотрим случай <tex>odd(H \setminus S) \; = \; 1 \;</tex>, <tex>|V_H| \; = \; n \; + \; k \leq ; = \; n \; + \; odd(G \setminus A) \; - \; |SA| \; </tex> т.к. , где <tex> A \; = \; arg \max\limits_{S \in V}(odd(G H \setminus S) \; - \; |S|) = k \; </tex>. Разность <tex>odd(G \setminus A) \; - \; |A| \; </tex> имеет ту же четность, что и <tex>n</tex>, поэтому <tex>|V_H|</tex> четно, значит, по лемме, мощность <tex>S</tex> нечетна, следовательно она не равна нулю, значит <tex> 1 \leq |S| </tex>.

* Если <tex>W \subset S \;</tex>, то <tex>odd(H \setminus S) \; = \; odd(G \setminus (S \cap V)) \; \leq \; |S \cap V| \; + \; k \leq |S| \; </tex>, так как <tex> \max\limits_{S \in V}(odd(G \setminus S) - |S|) = k \; </tex>. Таким образом, для графа <tex>H</tex> выполнено условие теоремы Татта, следовательно в нём есть полное паросочетание. Рассмотрим полное паросочетание в графе <tex>H</tex>, удалим вершины <tex>W</tex> из графа <tex>H</tex>. Количество непокрытых вершин после удаления не больше, чем количество удаленных вершин <tex>k</tex>, значит <tex>def(G) \; \leq \; k</tex>. Удалим множество вершин <tex>A \; = \; arg \max\limits_{S \in V}(odd(H \setminus S) \; - \; |S|) \; </tex> из графа <tex>G\;</tex>. Заметим, что после удаления в графе осталось <tex>odd(G \setminus A)\; </tex> нечетных компонент и образовались новые непокрытые вершины, но при этом число нечетных компонент больше числа удаленных на <tex>k</tex>. Значит хотя бы <tex>k</tex> нечетных компонент содержали исходно непокрытую вершину, следовательно <tex>def(G) \; \geq \; k \; </tex>. Из <tex>def(G) \; \leq \; k</tex> и <tex>def(G) \; \geq \; k \; </tex> следует <tex>def(G) \; = \; k \; </tex>.