An extension of Hall's theorem for partitioned bipartite graphs

• We have presented an extension of Hall's theorem in partitioned bipartite graph G.
• We have proved a necessary and sufficient condition for the existence of specific matching in G.
• We have showed that this matching can be computed in polynomial time.

Let G=(X,Y,E)G=(X,Y,E) be a bipartite graph with bipartition X and Y and edge set E such that X is partitioned into a set of k   pairwise disjoint subsets X1,X2,…,XkX1,X2,…,Xk. For any sequence n1,n2,…,nkn1,n2,…,nk of natural numbers with ni≤|Xi|ni≤|Xi| for all i, we prove a necessary and sufficient condition for the existence of a semi-perfect matching in G, a matching that includes, for each i  , at least nini edges that are incident to vertices from XiXi. Clearly, this is equivalent to Hall's theorem in the case where ni=|Xi|ni=|Xi| for all i.