# 2-edge colorable graph approximation

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?

• It should not be hard if true, but how do you guess this constant $3/4$ without having a proof? – Fedor Petrov Jan 12 '16 at 13:45
• 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? – Student Jan 12 '16 at 14:11