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.


2 Answers 2


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

  • $\begingroup$ Thanks, this sums it up. $\endgroup$
    – maverick
    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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.