A 2 edgecolorable 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 edgecolorable 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?
1

$\begingroup$ It should not be hard if true, but how do you guess this constant $3/4$ without having a proof? $\endgroup$ – Fedor Petrov Jan 12 '16 at 13:45

$\begingroup$ basically this problem can be seen as a special case of the maximum coverage problem, which for this problem would return this approximation. Can you help me? $\endgroup$ – Student Jan 12 '16 at 14:11