on theorem 5.3 in bondy and murty's book on matching and coverings

Question

On page 74 in Bondy and Murty's book, "Graph Theory with Applications", we have a proof of Theorem 5.3.

Theorem 5.3. In a bipartite graph, the number of edges in a maximum matching is equal to the number of vertices in a minimum covering.

Proof. Let $G$ be a bipartite graph with bipartition $(X,Y)$, and let $M^*$ be a maximum matching of $G$. Denote by $U$ the set of $M^*$-unsaturated verticse in $X$, and by $Z$ the set of all vertices connected by $M^*$-alternating paths to vertices of $U$. Set $S = Z \cap X$ and $T = Z \cap Y$. Then, as in the proof of Theorem 5.2, we have that every vertex in $T$ is $M^*$-saturated and $N(S)=T$. Define $\widetilde{K}=(X\setminus S) \cup T$. Every edge of $G$ must have at least one of its ends in $\widetilde{K}$. For, otherwise, there would be an edge with one end in $S$ and one end in $Y \setminus T$, contradicting $N(S) = T$. Thus $\widetilde{K}$ is a covering of $G$ and clearly $$\mathbf{|M^*|=|\widetilde{K}|}.$$ By Lemma 5.3, $\widetilde{K}$ is a minimum covering, and the theorem follows.

I can follow the whole proof except for the bolded step: "clearly $|M^*| = |\widetilde{K}|$". What am I missing? Thank you.

Answer 1

The proof already says that every edge of $G$ (in particular, every edge of $M^*$) has a vertex in $\widetilde{K}$.

Moreover, we can't have an edge of $M^*$ with two endpoints in $\widetilde{K}$: if $xy$ were such an edge, we'd need $x \in X \setminus S$ and $y \in T$. But then there's an $M^*$-alternating path from $U$ to $y$, which we can extend by the edge $xy$ to get an $M^*$-alternating path from $U$ to $x$.

So every edge of $M^*$ has exactly one endpoint in $\widetilde{K}$, and $|M^*| \le |\widetilde{K}|$.

To get the reverse inequality, we need every vertex in $\widetilde{K}$ to be $M^*$-saturated: to be the endpoint of an edge in $M^*$. This is spelled out in the proof:

• every vertex in $T$ is $M^*$-saturated by invoking the proof of Theorem 5.2.
• every vertex in $X \setminus S$ is $M^*$-saturated because the $M^*$-unsaturated vertices in $X$ were all put in $U$, and $U \subseteq S$.

SO every vertex in $\widetilde{K}$ is incident to an edge in $M^*$: to exactly one such edge, because $M^*$ is a matching. Therefore $|M^*| \ge |\widetilde{K}|$.

This took a while to write out, but it is "clear" from the figure in the textbook: the edges of $M^*$ are the bolded vertical edges, and each either has its top vertex in $X\setminus S$, or its bottom vertex in $T$, but not both.