  Erd\H{o}s, Gallai, and Tuza posed the following problem: given an $n$-vertex
graph $G$, let $\tau_1(G)$ denote the smallest size of a set of edges whose
deletion makes $G$ triangle-free, and let $\alpha_1(G)$ denote the largest size
of a set of edges containing at most one edge from each triangle of $G$. Is it
always the case that $\alpha_1(G) + \tau_1(G) \leq n^2/4$? We also consider a
variant on this conjecture: if $\tau_B(G)$ is the smallest size of an edge set
whose deletion makes $G$ bipartite, does the stronger inequality $\alpha_1(G) +
\tau_B(G) \leq n^2/4$ always hold?
  By considering the structure of a minimal counterexample to each version of
the conjecture, we obtain two main results. Our first result states that any
minimum counterexample to the original Erd\H{o}s--Gallai--Tuza Conjecture has
"dense edge cuts", and in particular has minimum degree greater than $n/2$.
This implies that the conjecture holds for all graphs if and only if it holds
for all triangular graphs (graphs where every edge lies in a triangle). Our
second result states that $\alpha_1(G) + \tau_B(G) \leq n^2/4$ whenever $G$ has
no induced subgraph isomorphic to $K_4^-$, the graph obtained from the complete
graph $K_4$ by deleting an edge. Thus, the original conjecture also holds for
such graphs.

Combinatorics