# Cardinality of any maximal matching is at least half the cardinality of a maximum matching

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.

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 $$A$$ is a maximal matching, then $$|A|\ge\frac12|B|$$ holds for any matching $$B$$, regardless of whether or not $$B$$ is a maximum matching.
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.
If neither $$p$$ nor $$q$$ is incident to any edge in $$B$$, we can add edge $$(p,q)$$ to $$B$$ and get a larger matching, contradicting the fact that $$B$$ is a maximum matching. That is, the fact that $$B$$ is a maximum matching is used to conclude that at least one edge in $$B$$ is incident with $$p$$ or $$q$$.
I think the phrase "at least one vertex of $$A$$" should be "at least one edge of $$A$$", and even then, I don't think it's well-phrased. I understand the proof to mean that each edge in $$A$$ is incident on at least one, and at most two edges in $$B$$.
• Thanks. But adding, as you suggest, $(p,q)$ to $B$ would first and most mean that $B$ is not maximal. So assuming $B$ only maximal would have sufficed. But this is not the case, since the statement is assuming a stronger property, which is $B$ be maximum and not only maximal. Jan 18, 2020 at 10:42