In Graph Theory lecture, I'm struggling to solve the problem about the maximal matching of a graph, form the textbook written by Bondy & Murty.
Let $M$ be a matching of a graph $G$, and let $B \subseteq V(G)$ such that $\lvert U \rvert = o(G-B) – \lvert B \rvert$ where $U$ denote the set of vertices not covered by $M$. Prove that $M$ is maximal.
By searching, I found that such a set $B$ is called a barrier. I tried to solve it by using the inequality $$ \lvert U \rvert \geq o(G-S) – \lvert S \rvert, \forall S \subset V(G),$$
and that if the equality holds, then $M$ does not cover as few vertices as possible. However, I have been stuck since the set $U$ depends on the choice of $M$, that is, $U$ is not fixed.
I also tried to prove by contradiction, that assuming $M$ is not maximal. But such an approach needs to construct another matching which will contradicts the assumption, I think, which was also difficult for me.
It will be glad if someone give me how to approach the problem.
Best Answer
Using that inequality, we know that every matching must leave at least $o(G-B) - |B|$ vertices uncovered. Since $M$ leaves exactly that many vertices uncovered, it has the most edges possible: it is not only maximal but maximum.
For completeness, here is a proof of the inequality.
First, let $M'$ be the matching where we delete all edges of $M$ with an endpoint in $S$, and $U'$ be the corresponding set of uncovered vertices. Then $|U'| \le |U| + 2|S|$, because we deleted at most $|S|$ edges.
However, $|U'| \ge o(G-S) + |S|$, because:
So $|U| \ge |U'| - 2|S| \ge o(G-S) - |S|$.