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?