I'm dealing with the following problem in graph's matchings. Let G = (V,E) be an undirected graph, and let S,T subgroups of V be two sets of vertices with no common neighbours. That is, there exist no vertices s in S, t in T, and v in V such that (s,v) (t,v) in E (note that there may still be edges between S and T or within S or T).
I wanna show that if there exists a matching in G in which all vertices in S are covered, and also a (possibly different) matching in which all vertices in T are covered, then there also exists a matching in G in which all vertices in S union T are covered.
An idea: dividing M1 and M2 (the two matchings for S,T accordingly) to groups of different edges: 1 - Edges from S to S 2 - Edges from S to T 3 - Edges from S to an unmatched vertex (harmless edges).
Same for T.
I think the first thing to do in order to show such matching exists, is take edges from group 3 first, that will make our problem smaller. Or perhaps there's a counter example? Any ideas?