Minimal amount of edges needed to be removed to make a graph triangle free (approximation algorithm)

Question

Given a graph G = (V,E) there is a minimal number of edges - k - that need to be removed to make G triangle free. I'm trying to find an approximation algorithm (that is as efficient as possible) that finds a set of edges to remove to make G triangle free that is no larger than 3k. Can someone help me?

Answer 1

Try the greedy algorithm: in each step, eliminate the biggest possible number of triangles by deleting the edge contained in the most triangles.