In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of graphs with perfect matchings.
Let ${\displaystyle o(X)}$ be the number of odd components of the subgraph induced by ${\displaystyle X}$.
Theorem (Tutte's 1-Factor Theorem (1947)) A graph $G$ has 1 factor if and only if for any $S\subset V(G)$,
$$o(G-S)\le |S|.$$
My problem: If a graph $G$ has a perfect matching, does that mean that there is a $S$ such that $|S|$ is equal to $o(G-S)$?
This fact seems to be seen in the generalized Tutte-Berge formula which says that the size of a maximum matching of a graph $G=(V,E)$ equals $$\frac{1}{2} \min_{S⊆V}(|V|−(o(G−S)-|S|))$$
If for any $S$, we have $o(G-S)<|S|$. Then according to the above formula the size of maximum matching is strictly greater than $\frac{1}{2}n$, which is not possible.
However, I feel that the above explanation relies too much on the Tutte-Berge formula which seems unnatural. Can we directly explain it from the Tutte 1-Factor theorem?
Best Answer
If $G$ has a perfect matching, then $o(G-S) = |S|$ whenever $|S|=1$. Indeed, for $|S|=1$, $o(G-S)$ is either $0$ or $1$. Since $G$ has a perfect matching, $G$ has an even number of vertices, so $G-S$ has an odd number of vertices, and thus $o(G-S) = 1 = |S|$.