2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I have think over several hours but still unsuccessful. $\endgroup$
    – Joe Li
    Oct 11 '13 at 13:22
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ This might work but I'm expecting a much easier answer, which should involve connected component. $\endgroup$
    – Joe Li
    Oct 11 '13 at 14:35
  • $\begingroup$ Okay it has an odd number of edges. Why does this imply it has a pair of two neighboring ones that are either M1 or M2? You could have e1, e2,..,e_(2n), e_(2n+1) interchangeably. What I would say is that because the first and last vertices are equal then also the second and second to last must be, for the first and last edges are from the same M1 or M2. But a vertex cannot appear twice on a cycle, except the fist and last. $\endgroup$
    – Cantor
    Oct 10 '21 at 11:50
  • $\begingroup$ "You could have e1, e2,..,e_(2n), e_(2n+1) interchangeably." You could, but then $e_1$ and $e_{2n+1}$ belong to the same matching. However, this being a cycle, they are also connected, which is a contradiction with the definition of a matching. $\endgroup$ Oct 11 '21 at 11:13
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.