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.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

