1
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – user249018
    Jan 18, 2020 at 10:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .