Problem 167

Erdős Problem #167 [status: falsifiable; formalized: no]. If $G$ is a graph with at most $k$ edge disjoint triangles then can $G$ be made triangle-free after removing at most $2k$ edges? Current best: The trivial bound of $\leq 3k$ was improved to $\leq (3-\frac{3}{23}+o(1))k$ by Haxell [Ha99]. Prize: no. Tags: graph theory.