1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Such a proof certainly sounds constructive to me, if it gives an algorithm for finding a set $S$. Do you mean that the proof does not tell you how to find a perfect matching in case Tutte's condition holds? $\endgroup$
    – Misha Lavrov
    Jan 27, 2021 at 22:12
  • $\begingroup$ The proof would be constructive if it helped in finding a 1-factor given that Tutte's condition holds, but it does not. The proof builds an edge-maximal graph G' containing G that does not contain a 1-factor, and finds a set S that violates Tutte's condition in G'. Building such a G' would require a decision procedure that answers whether a graph contains a 1-factor or not. Do I need to describe the proof more in my question? $\endgroup$
    – Abhishek
    Jan 27, 2021 at 22:23
  • $\begingroup$ If your objection is that the proof does not help find a perfect matching, then you're in some trouble: the simplest algorithm to do that is the blossom algorithm, which sounds already like a very complicated proof. $\endgroup$
    – Misha Lavrov
    Jan 27, 2021 at 22:42
  • $\begingroup$ On the other hand, we can use the blossom algorithm to construct the set $S$ in Tutte's theorem in cases where a perfect matching is not found, so if you consider that a constructive proof, then that's how you'd do it. $\endgroup$
    – Misha Lavrov
    Jan 27, 2021 at 22:53
  • $\begingroup$ You have already answered my question. Constructive proofs can be found by tracing backwards from Edmonds, J. "Paths, Trees, and Flowers." Canad. J. Math. 17, 449-467, 1965 to "Two Theorems in Graph Theory", C. Berge, 1957. $\endgroup$
    – Abhishek
    Jan 27, 2021 at 23:03

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.