Изменения

|statement= <tex>def G = \max\limits_{S \in V} (odd(G \setminus S) - |S|)</tex>

|proof=

Если не <tex>W \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>\forall S \in G : 0 \; \leq \; |S|</tex>. Рассмотрим случай <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>.

}}