Изменения

Если <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>k \; \leq \; def(G)</tex>. Значит, <tex>def(G) \; = \; k</tex>. Теорема доказана.