I have been reading the Chapter on Matchings in Graph Theory, R. Diestel, Fifth Edition, and have just encountered the proof of Tutte's theorem. The statement of the theorem is:
A graph $G$ has a $1$-factor if and only if $q(G-S) \leq |S|$ for all $S \subseteq V(G)$.
The forward direction for the proof is trivial. For the other direction, the first step says:
Let $G = (V, E)$ be a graph without a 1-factor. Our task is to find a bad set $S ⊆ V$, one that violates Tutte’s condition.
Thus, the contrapositive is being proven, which is not a constructive step. I tried searching for proofs of Tutte's theorem online that differed from the Diestel version but was not successful. Is a constructive proof known for Tutte's Theorem?
The motivation behind the question is that Hall's Theorem (the preceding section in the book) has several constructive proofs that offer insight into how to find maximal matchings but I haven't found the proof for Tutte's theorem to be particularly insightful (yet).