Matching cardinality graphs

Question

Show that a graph $G$ contains a matching of cardinality $p$ if and only if $q(G−S) \le |S|+|G|−2p, ∀S ⊆ V (G)$.

//Again a problem that i encountered in my book about graphs theory.Any tip would be appreciated//

Answer 1

I'm assuming the notation $q(G - S)$ denotes the number of odd components in $ G - S$, and that $|G|$ is the number of vertices in the graph.

The Tutte-Berg formula is most useful in this situation.

Theorem (Tutte-Berg). Where $\nu(G)$ denotes the size of a maximum matching of $G$, \begin{equation} \nu(G) = \frac{1}{2} \min_{U \subseteq V(G)}( |U| - q(G - U) + |V(G)|). \end{equation}

For neccesity, it is clear that if we have a matching of size $p$, then $p \leq \nu(G)$. Moreover, for any $S \subseteq V(G)$ \begin{align} p \leq \nu(G) &\leq \frac{1}{2}(|S| - q(G - S) + |G|)\\ \implies 2p &\leq |S| - q(G - S) + |G|\\ q(G - S) &\leq |S| + |G| - 2p. \end{align} We are done this direction since $S$ was arbitrary.

Conversely, it is enough to show that $p \leq \nu(G)$ since if we can find a maximum matching $M$ then restricting $M$ so that the number of edges is $p$ allows us to conclude. Suppose for sake of a contradiction that $p > \nu(G)$ (remember, we don't know if there is a matching of size $p$ yet). Clearly then $-2p < \nu(G)$ and for some $S\ \subseteq V(G)$ satisfying $\nu(G) = \frac{1}{2} ( |S| - q(G - S) + |G|)$ from the formula, we have \begin{align} q(G - S) &\leq |S| + |G| - 2p\\ &< |S| + |G| - 2\nu(G)\\ &= |S| + |G| - (|S| - q(G - S) + |G|)\\ &= q(G - S). \end{align} That is, $q(G - S) < q(G - S)$, a contradiction. Therefore, $p \leq \nu(G)$ as desired, allowing us to conclude.