I'm sure it is well-known how many edges you must delete in a (highly linked) graph to destroy all cycles. Is it also known how many edges you must delete to destroy only all triangles? And even, how many you need if additionally, you may not use an edge to destroy more than one triangle? (Note the latter doesn't mean you can't touch a common edge, but after deleting this edge only one triangle "counts" as destroyed. Thus you need 4 edges for the graph $K\_4$, and $K\_6$ has no solution.)  

A reference would be welcome, especially if the problem would be in NP (but a non-NP lower bound around $O(n^2)$ would also be fine).



Deleting triangles in a graph
Given a graph $G$, the problem of determining the minimum size $\tau(G)$ of a set of edges $X$ such that $G-X$ is triangle-free is indeed NP-complete. This was proved by [Yannakakis](https://epubs.siam.org/doi/abs/10.1137/0210021?journalCode=smjcat). Regarding bounds for $\tau(G)$, we can consider the following dual problem. Let $\nu(G)$ be the maximum number of edge-disjoint triangles of $G$. Clearly $\nu(G) \leq \tau(G) \leq 3\nu(G)$. A famous conjecture of Tuza asserts:



> 
> $\tau(G) \leq 2\nu(G)$, for all graphs $G$.
> 
> 
> 


The complete graph $K\_4$ shows that this bound is best possible. Tuza's conjecture is still open, but it has been shown to hold for many restricted graph classes. For example it holds for threshold graphs by this recent [paper](https://arxiv.org/abs/2105.09871) of Bonamy, Bożyk, Grzesik, Hatzel, Masařík, Novotná, and Okrasa. The best general bound is by [Haxell](https://www.sciencedirect.com/science/article/pii/S0012365X98001836), who proved that $\tau(G) \leq \frac{66}{23} \nu(G)$ for all graphs $G$.


