Изменения

Таким образом, для графа <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>. Заметим, что после удаление в графе осталось несколько нечетных компонент и образовались новые непокрытые вершины, но при этом осталось на k больше нечетных компонент, чем мы удалили, значит, хотя бы k нечетных компонент содержали исходно непокрытую вершину, значит, <tex>k \leq def(G)</tex>. Значит, <tex>def(G) = k</tex>. Теорема доказана.