Show the union of two matching is bipartite

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

Using the definition in the hint, I think this kind of argument would work. Define the arbitrary partitions to be P1 and P2. Let v be a node from G. Let v and every node that is not part of its connected component be in P1. All others go in P2. Now M1 is obviously bipartite. Notice that every node has at most degree 2. The case where every node has degree 1 is trivial. If there is a node of degree 2, then the vertices conneted to it must be in M2. Notice that connections amongst the vertices in M2 isn't possible, since it would mean that either in M1 or M2 had neighbouring edges. Hence the union of two matchings must be bipartite.

Answer 5

If a graph is the union of two matchings ($M_1$ and $M_2$) then it's $2$-edge-colorable. (Color the edges of $M_1$ blue, the edges of $M_2\setminus M_1$ red.)

If a graph is $2$-edge-colorable, it has no odd cycles.

A graph with no odd cycles is bipartite.

Answer 6

One way is to approach using induction on no of edges in $M_2$,keeping the invariant that the subgraph formed is bipartite at each step Remember in a matching each vertex appears only once . Let $S$ be set of 1st n edges of $M_2$ then

$P(n)$: The graph formed $G'$ by taking $G'=\{V,M_1 \cup S \}$ is bipartite .i.e can be divided into 2 sets of vertices $V_l$ and $V_r$ such that all edges lie between the 2

$P(0)$ is vacuously true

Assuming $P(n)$ ,let edge be $e,e\in M_2,e =(u,v)$ be the edge to be added in $(n+1)^{th} $step. We can have two cases 1)$e\in M_1$, then graph is bipartite by P(n) 2)$e \notin M_1$ then goal is to find a partition $V_l$ and $V_r$ which can do the job.Let $(u,x)\in M_1$ and $(v,y)\in M_1$ So we can find the partition $V_l$ consisting of $u$ and $y$. Similarly $V_r$ consisting of $x$ and $v$ or viceversa. Hence graph $G'$ still remains bipartite .Remember edges (x,v) and (u,y) can't be present in $M_2$ as each vertex can come only once.