Show the union of two matching is bipartite

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.

-
I have think over several hours but still unsuccessful. – Joe Li Oct 11 '13 at 13:22

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.

-
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.

-

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.

-