# Maximal Matching in Bipartite Graphs

Maximal matching for a Biparitie Graph is the maximum cardinality set of edges such that no two edges share any vertex.

We are given a biparitie graph and let's say there is only one edge $$E$$ that has vertex $$X$$ as one of its end-point.
I feel it is always safe to include the edge $$E$$ in the maximal matching because the given graph is biparitite in nature.

Can we prove this? I have worked on the proof which seems to justify this, but I am not satisfied with it.

My Approach towards the Proof:

Picking an edge $$(X,Y)$$ for maximal matching is wrong if there exist edges $$(X,A)$$ and $$(Y, B)$$. Clearly, picking $$(X,Y)$$ increases set of maximal matching by one, but we could have picked the other two edges and increase the cardinality by two.
In case there is only one edge $$E$$ having vertex $$X$$ as one of its end-point, we never come into the situation of missing out two edges when we include this one.

I think you have the correct idea. Maybe we can formalize it little more.

Let $$G$$ be a bipartite graph and $$X$$ and $$Y$$ are bipartitions of $$V(G)$$. Also let $$x\in X$$ be a vertex with degree $$1$$ and $$e = xy$$ be the edge incident to $$x$$. So, the edge that is connected to $$x$$ is connected to $$y \in Y$$. Then the claim should be there exists a maximal matching containing $$e$$ because we can find an example where there is a maximal matching does not contain $$e$$ with the same number of edges (but your claim is just to include $$e$$ to maximal matching safely so I don't think this is important here).

Now, let $$M$$ be the maximal matching with $$|M|$$ edges including $$e$$. Suppose for a contradiction that there exists a matching $$M'$$ with $$|M'| \ge |M|+1$$. Since $$M$$ is the maximal matching including $$e$$, $$M'$$ cannot include $$e$$. Therefore, only possibility for this matching is to include $$ay$$ as an edge where $$a \in X$$. Then we can remove $$ay$$ and add $$e=xy$$ to $$M'$$ without changing $$|M'|$$. But then our new matching is a matching that includes $$e$$ and with size $$|M'| > |M|$$, contradictory to the assumption that $$M$$ is the maximal matching including $$e$$.

• Thanks, this sums it up. Jun 1, 2019 at 18:59

Assume you are given a maximal matching in the graph.

Let $$E = \{X, Y\}$$.

If there is no edge in this matching that connects $$Y$$, you can safely add $$E$$ to the matching without violating the matching property. But this means that the matching is not maximal.

If there is an edge connecting $$Y$$, replacing it with $$E$$ will preserve the matching property and the new matching will have the same cardinality.

So there exists a maximal matching containing $$E$$.

But this does not mean that any maximal matching contains $$E$$, however.