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

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.

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

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.