Correctness of proof regarding matchings in graph

Question

Proof: By contradiction. Assume $G'$ is not a bipartite graph, that is, the set of vertices $V$ can't be partitioned into sets $L$ and $R$ such that every edge is incident to a vertex in $L$ and to a vertex in $R$. Thus $G'$ requires at least 3 colors.

Thus $G'$ must have at least 1 cycle of 3 vertices (as it requires at least 3 colors). Let the cycle be $v_i, v_{i+1}, v_{i+2}, v_i$. Each of the edges in the cycle belong to either $M_1 or M_2$. Without loss of generality, assume $v_i - v_{i+1}$ belong to $M_1$. Therefore, $v_{i+1} - v_{i+2}$ must belong to $M_2$. Now $v_{i+2} - v_{i}$ can't belong to either $M_1 or M_2$. We have reached a contradiction and thus $G'$ must be bipartite.

---

I wrote the above proof but am not sure if it is correct. Need someone to verify its correctness.

Answer 1

Your proof assumes a 3-cycle, but in fact it should be extended slightly to cover any odd-length cycle - $C_5$ (or any other odd cycle graph) cannot be 2-colored.

You can use a similar concept to that in your proof to show that any cycle in $G'$ is of even length, and thus $G'$ is bipartite:

• Suppose $v_1v_2\ldots v_nv_1$ is a cycle in $G'$. Then successive edges in the cycle cannot belong to the same matching, so must belong alternately to $M_1$ and $M_2$, including the edges $v_nv_1$ and $v_1v_2$. Thus the cycle is even in length.