Barrier and Maximal Matching of a Graph

Question

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.

Answer 1

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:

• $M'$ is also a matching in $G-S$ now, so it must leave a vertex uncovered in every odd component of $G-S$.
• Also, every vertex in $S$ is uncovered by $M'$.

So $|U| \ge |U'| - 2|S| \ge o(G-S) - |S|$.