Is a constructive proof known for Tutte's Theorem?

Question

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).

Answer 1

The next theorem in the book (Graph Theory, Diestel, 5th Ed.) is a stronger result that implies Tutte's theorem. The theorem says:

Every graph $G = (V,E)$ contains a vertex set $S$ with the following two properties: (i) $S$ is matchable to $C(G−S)$; (ii) Every component of $G − S$ is factor-critical. Given any such set $S$, the graph $G$ contains a 1-factor if and only if $|S| = |C(G−S)|$.

The proof of this theorem in the book is constructive: the largest set $T$ that satisfies the following property also satisfies the two properties in the theorem:

$$\forall U \subseteq V(G): q(G-U) - |U| \leq q(G-T) - |T|$$

If $|T| = |C(G-T)|$, then a 1-factor exists for $G$ that contains all the (contracted) edges between $T$ and $C(G-T)$; the remaining parts of the 1-factor may be constructed by recursively repeating the process for all the components in $C(G-T)$. Thus, an interesting algorithm for finding a 1-factor is present in this constructive proof.

I wish I had been more patient with the book before asking the question, but this answer may be useful for others reading the book.