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?


Hint: Try to cover $S$ first, and then cover $T$. The first step must be done as minimally as possible so that the second step works.

  • $\begingroup$ @Jojo Ignore my previous ideas. This is the correct way to go... $\endgroup$ Feb 14 '15 at 16:07
  • $\begingroup$ Not sure I understand. What is the correct way to go? Because I haven't succeeded yet with my idea. $\endgroup$
    – itaymeller
    Feb 14 '15 at 19:05
  • $\begingroup$ @Jojo If you saw the previous revisions of the post, ignore them. This latest one is correct. One of the groups need to be covered first before the other. $\endgroup$ Feb 15 '15 at 3:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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