Suppose a bipartite graph $G=(V\_1 \cup V\_2, E)$ is given, and one is interested in matching vertices $V\_1$ to vertices $V\_2$. Assume Hall's condition does not hold, so a perfect matching does not exist. What is a good lower bound on the amount of vertices in $V\_1$ which can be matched? I am not interested in algorithmic approaches.



Good lower bound on matching in bipartite graph
Let $d$ denote the *deficiency* of the graph, i.e., the maximum difference between the a size of a subset of $V\_1$ and the number of its neighbors (#vertices $-$ #neighbors).


If $d \leq 0$ then the condition holds and the graph has a matching. Otherwise, there is a matching of size $|V\_1| - d$.


To see why, add to $V\_2$ a set of $d$ "imaginary" nodes, connected to all vertices of $V\_1$. Then the condition holds for the new graph, and there is a matching for all vertices in $V\_1$. Ignoring the $d$ neighbors of imaginary vertices, the remaining $|V\_1| - d$ vertices of $V\_1$ are matched to "real" vertices in $V\_2$. 


