Изменения

Рассмотрим случай <tex>odd(H \setminus S) \; = \; 1 \;</tex>, <tex>|V_H| \; = \; n \; + \; k \; = \; n \; + \; odd(G \setminus A) \; - \; |A|\; </tex>, где <tex>A \; = \; arg \max\limits_{S \in V}(odd(H \setminus S) \; - \; |S|) \; </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>. Теорема доказана.