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.

  • $\begingroup$ 0. If you insist that your graph has edges then 1 (think $K_{1,n}$). Your question is not well formulated. $\endgroup$ – Chris Godsil Jan 16 '13 at 13:55

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

| cite | improve this answer | |

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.