Multigraphs (only) satisfy a weak triangle removallemma

摘要

The triangle removal lemma states that a simple graph with o(n3) triangles canbe made triangle-free by removing o(n~2) edges. It is natural to ask if this widelyused result can be extended to multi-graphs. In this short paper we rule out thepossibility of such an extension by showing that there are multi-graphs with onlyn~(2+0(1))triangles that are still far from being triangle-free. On the other hand, weshow that for some slowly growing function g(n) = w(1), if a multi-graph has onlyg(n)n~2triangles then it must be close to being triangle-free. The proof relies onvariants of the Ruzsa-Szemeredi theorem [15].