Let $X,Y$ be a bipartite graph and $X',Y'$ be two subsets of the vertices. Is there a Hall type theorem for the existence of matchings saturating both subsets simmultaneously?


Clearly necessary conditions are for a saturating matching to exist in $X'\cup Y$ and $X\cup Y '$ but I don't know if this is sufficient.



Hall type theorem for saturations of subsets of bipartite graphs
Your necessary condition is also sufficient. Let $M\_1$ and $M\_2$ be the matchings from $X'$ to $Y$ and from $Y'$ to $X$. The union of $M\_1$ and $M\_2$ is a bipartite graph of maximum degree at most $2$, so has as connected components paths and even length cycles.


On the cycle components, taking alternate edges around the cycle covers the same set of vertices by independent edges. This also works on path components with an odd number of edges.


For path components with an even number of edges, the first and last vertices are in the same half of the graph; so the path starts and ends in $X$, say. If either endpoint is not in $X'$ then we can delete the corresponding edge to obtain a path with an odd number of edges covering the same subset of $X' \cup Y'$. So we're left only with the case where one component is a path joining two vertices of $X'$. But both of these vertices are in $M\_1$, and at least one is in $M\_2$ (as the path has an even number of edges), so at least one of these vertices has degree $2$, and therefore can't have been an endpoint.


