What I understand
I understand how they're picking U. I understand that M is a maximal matching so that if the minimum cover cover all edges in G, then it must necessarily cover all edges in M because M is a subset of E.
I understand that the size of the minimum cover can't be less than the size of M because it takes atleast |M| vertices to cover |M| edges where none of the vertices is incident with more than one edge.
Ok. So I think the idea of the proof is to show that if any neighboring vertices, a and b (elements of E), are in U (a set that covers M), then we can say that U covers E. And since U has a size of |M| (a size that it can't be less than), then this is the minimum cover. Is that right?
What I don't understand
The proof loses me when it introduces a' and b'. I don't understand how they fit into this proof.
Would appreciate some help.
Thank You
Best Answer
$M$ is a maximal matching, and we’re assuming that $ab\notin M$. There must be either an edge in $M$ incident at $a$ or an edge in $M$ incident at $b$, because if not, we could add the edge $ab$ to $M$ to get a strictly bigger matching. Thus, either $a$ is matched (but not with $b$), and there is a $b'\ne b$ such that $ab'\in M$; or $a$ is not matched, and there is an $a'\ne a$ such that $a'b\in M$.
Suppose that $a$ is not matched, so that there is an $a'\ne a$ such that $a'b\in M$. Then $ab$ is an alternating path: it starts in $A$ at the unmatched vertex $a$, its first edge is not in $M$, and we don’t have to worry about later edges because there aren’t any. The edge $a'b\in M$ has one of its ends in $U$: since the end $b$ is the end of an alternating path, it’s the end of $a'b$ that we put into $U$. Thus, $b\in U$, and we’re done: $U$ covers the edge $ab$.
Thus, we may assume that there is a $b'\ne b$ such that $ab'\in M$. If $a\in U$, we’re done: once again $U$ covers the edge $ab$. Assume, then, that $a\notin U$. Then $b'$ must have been the end of $ab'$ chosen to go into $U$, so there must be an alternating path $P$ ending at $b'$. If vertex $b$ is in the path $P$, we can cut $P$ short at $b$ to get an alternating path $P'$ (that Diestel denotes by $Pb$) ending at $b$. If $b$ is not in $P$, we can extend $P$ by adding the edges $b'a$ and $ab$ to get again an alternating path $P'$ (that Diestel denotes by $Pb'a'b$) ending at $b$. Thus, in all cases there is an alternating path ending at $b$. If $b$ were unmatched by $M$, $P'$ would be an augmenting path, and we could extend $M$ to a larger matching. $M$, however, is maximal, so this is impossible, and $P'$ therefore cannot be an augmenting path. This in turn means that $b$ cannot be unmatched: it must be one end of some edge $e$ in $M$. And since it’s also an end of an alternating path, it must have been the end of $e$ that was put into $U$. Thus, $b\in U$, and yet again we find that $U$ covers the edge $ab$.
And $ab$ was arbitrary, so every edge of the graph has at least one of its ends in $U$, meaning that $U$ is a vertex cover of the edges. Finally, we put one vertex into $U$ for each edge of $M$, so $|U|=|M|$, as desired.