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.
1
-
$\begingroup$ 0. If you insist that your graph has edges then 1 (think $K_{1,n}$). Your question is not well formulated. $\endgroup$– Chris GodsilCommented Jan 16, 2013 at 13:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.
