Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $G=(V,E)$ be a graph.

Let $M1, M2$ be two matchings of $G$. Consider the new graph $G' = (V, M1 ∪ M2)$ (i.e. on the same vertex set, whose edges consist of all the edges that appear in either $M1$ or $M2$). Show that $G'$ is bipartite.

Helpful definition: A connected component is a subgraph of a graph consisting of some vertex and every node and edge that is connected to that vertex.

share|improve this question
    
I have think over several hours but still unsuccessful. –  Joe Li Oct 11 '13 at 13:22

3 Answers 3

Assume that $G'$ has a cycle of odd length. Then it has odd number of edges, so some pair of two neighboring ones has to be in either $M_1$ or in $M_2$. But then $M_1$ (or $M_2$) is not a matching, which is a contradiction.

We conclude that $G'$ has only even cycles (or no cycles at all).

Now use this.

share|improve this answer
    
This might work but I'm expecting a much easier answer, which should involve connected component. –  Joe Li Oct 11 '13 at 14:35

The graph induced by a matching has maximum degree 1, and a graph whose edges are formed from the union of two matchings $M_1,M_2$ has maximum degree at most 2. Thus, we have a graph $G'=(V,M_1 \cup M_2)$ whose maximum degree is at most 2. A graph having maximum degree at most 2 is necessarily a disjoint union of paths and cycles (for if a component contains a cycle, it can't contain anything else besides this cycle since a vertex cannot have degree more than 2). To prove $G'$ is bipartite, we need to prove that if one of the components of $G'$ is an odd cycle, there is a contradiction. Assign each edge in the first matching color 1, and each edge in the second matching color 2. Thus $G'$ can be properly edge-colored using at most 2 colors, whereas an odd cycle requires 3 colors for its edges.

share|improve this answer

A Graph is bipartite if and only if it has no odd cycles. As stated in the above answers the symmetric difference between M1 and M2 consists of only paths and even cycles.Thus the graph of M1 symmetric difference M2 is bipartite.Now you only need to add edges which belonged to both M1 and M2 it can trivially be seen that after adding these edges the graph will still continue to be bipartite.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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