Let $G=(V,E)$ be a an undirected graph. Then, the cardinality of any maximal matching is at least half the cardinality of the maximum matching of $G$. Here is the prove in the lecture:
Let $A$ be am arbitrary maximal matching of $G$ and $B$ a maximum matching. In view of proving by contradiction, we assume that $ \vert A \vert < \frac {1}{2} \vert B \vert .$ For every edge $(p,q)\in A$, there exits at least one but at most $2$ edges in B that are incident on some vertex of $A.$ Thus, at most $2\vert A \vert$ edges in $B$ are incident on some vertex in $A$. Let $a$ be the number of edges in $B$ that are incident on some index in $A$. Combined with the assumption this means, $a \leq 2 \vert A \vert < \vert B \vert.$ The strict inequality to the right means that there must exist an edge $d \in B$ that is not incident on any vertex in $A.$ Thus, $A$ is not maximal.
What I don't understand in the proof is that it is nowhere used the requirement that $B$ be maximum, i.e. $\vert A \vert \leq \vert B \vert$. Can somebody help me figure out why? I thank you.
Best Answer
You are quite right, that the proof does not use the assumption that $B$ is a maximum matching. Therefore the proof actually proves a more general result than the one that was stated, namely:
If you think about it a little, I think you will understand why, if $A$ is at least half as big as the maximum matching, then it is also at least half as big as any smaller matching; and why nobody bothers to state the result in the "more general" form.