I'm studying Tutte's theorem. There is a proof in Graph Theory / Diestel. I took a very short glance at it before trying to prove it on my own. I am giving my proof attempt here with a specific question.
For a finite graph $G=(V,E)$ and a subset of vertices $S \subset V$, we let $q(S)$ denote the number of connected components of odd size in the graph induced on $V \setminus S$.
Tutte's theorem then says that if $q(S) \leq |S|$ for any $S \subset V$ (I call this Tutte's condition), then there is a perfect matching in $G$.
(the converse is trivially true too).
I'm trying to prove it in the following way: Iteratively remove edges from $G$ without violating Tutte's condition. We get a graph satistying Tutte's condition, for which a removal of any edge would violate Tutte's condition. I claim that all edges are of degree $1$ in this new graph. Thus it is a $1$-factor in the original graph and we are done.
First, vertices of degree $0$ are impossible because they violate Tutte's condition with $S=\emptyset$.
Now, assume there is a vertex $v \in V$ such that $deg(V) \geq 2$. Let $u$ and $w$ be 2 of its neighbours. Thus, removal of either edge $vu$ or $vw$ would result in violation of Tutte's condition. It is thus sufficient to prove the following lemma:
Lemma: For a graph $G=(V,E)$, if removal of edge $vu$ results in violation of Tutte's condition as exhibited by the set $S_1 \subset V$ and removal of edge $vw$ results in violation of Tutte's condition as exhibited by the set $S_2$, then $G$ itself violates Tutte's condition as exhibited by the set $S_1 \Delta S_2 = (S_1 \cup S_2) \setminus (S_1 \cap S_2)$.
Is this lemma true and how can it be proved?