Can Hall's Marriage Theorem Determine a Matching of Size T in Bipartite Graphs?

[bodensee9]

Hello,

I need to show that for a bipartite graph G(X, Y, E), if I have

|R(A)| = range of a subset A of X = the number of vertices incident to a vertex in A.
|A| = cardinality of A

So if I have |R(A)| >= |A| - |X| + t, then there is a matching of size T.

I thought of the following, but it seems fishy:

I know that if I want an X matching, then |R(A)| has to equal or be greater than |A|.
SO if I added |X| - t new vertices to Y and connected those all to my vertices in X, then I know that there will be at least a |X| - t matching, plus whatever matching there existed in the first place (before I added the |X| - t new ones). So then in this case, |R(A)| >= |A| for a full X matching. But suppose I removed those vertices that I just added, then

|R(A)| - (|X| - t) = |A| - (|X| - t),

But then I don't know what size of a matching this would give me. Would this give me the matching of the t elements because originally I had a matching of |X|, but now since I am substracting |x| - t elements, I only have |x| - |x| + t or t matching?

Thanks.

 

[kurt.physics]

Yes, this logic is correct. If |R(A)| >= |A| - |X| + t, then we know that there must be at least t edges in the matching. This is because the range of A is equal to the number of vertices incident to a vertex in A, and since |R(A)| >= |A| - |X| + t, then it means that there must be at least t edges in the matching.