2-edge colorable graph approximation

Question

A 2 edge-colorable graph is a graph in which we can color the edges with two colors, in a way such that no edges of the same color share a vertex. Given a graph G = (V,E) I want to find a 2 edge-colorable subgraph of G that has the maximum number of edges. Currently i am using this algorithm. I find a maximum size matching M1 in G and then I find a maximum size matching M2 in G - M1. I would like to show that this algorithm can grant me a 3/4 approximation of this problem. Can anyone help me proving that?

Answer 1

Each $2$ edge-colorable subgraph $H$ of $G$ is a union of vertex disjoint paths or cycles of even length. Let $H$ be a maximum size $2$ edge-colorable subgraph $H$ of $G$, $m=|E(H)|$, and $M_1$ be a maximum size matching in $G$. Since each monochromatic set of edges constitutes a matching, $m_1=|M_1|\ge |E(H)|/2=m/2$. Next, since a subgraph of a $2$ edge-colorable graph is $2$ edge-colorable, in the set $E(H)\setminus M_1$ we can find a matching of size at least $|E(H)\setminus M_1|/2$. Then $$m_1+m_2=|M_1\cup M_2|\ge m_1+|E(H)\setminus M_1|/2\ge $$ $$m_1+(m-m_1)/2=(m+m_1)/2\ge (m+m/2)/2=3m/4.$$