Bipartite Matching Proof

47 Views Asked by At

Let $G=(V,E)$ be a bipartite graph $|L| = |R| = n$

Given the graph G has no perfect matching how can i prove that G has $L_1$ $\subset $ L and $R_1 \subset R $ such that $|L_1| + |R_1| = n+1$ and $L_1$ isn't connected to $R_1$

if G have no perfect matching so there X in L (or R) such that |X| > |N(X)| but im kinda lost how can i apply this for this proof i will appreciate any helpers!