In Zsolt Tuza's [Unsolved combinatorial problems I](http://www.brics.dk/LS/01/1/BRICS-LS-01-1.pdf), Problem 46 is the following conjecture:


Let $G$ be a graph on $n$ vertices. Let $\alpha\_1$ be the maximum number of edges of $G$ such that every triangle in $G$ contains at most one of these edges. Let $\tau\_1$ be the minimum number of edges of $G$ such that every triangle in $G$ contains at least one of these edges. Then, it is conjectured that $\alpha\_1+\tau\_1 \leq \dfrac{n^2}{4}$.


The reference given is [Paul Erdös, Tibor Gallai, Zsolt Tuza, *Covering and independence in triangle structures*, Discrete Mathematics 150 (1996) pp. 89-101](http://www.sciencedirect.com/science/article/pii/0012365X9500178Y). However, in this reference, the conjecture is only formulated (Conjecture 11) for the case when $G$ is a triangular graph (i. e., every edge of $G$ is contained in a triangle). Maybe I am missing something completely obvious, but is this really equivalent, or did Tuza extend his conjecture after this publication? Or is one of the statements wrong resp. mistakenly specialized? (Note that the conjecture for generic $G$ clearly generalizes Turan's theorem for $K\_3$'s, but in the triangular case I don't see how it yields Turan.)


(Also, are there any news on this question?)



What is the correct statement of this Erdös-Gallai-Tuza problem generalizing Turan's triangle theorem?
I hope I am not violating any kind of MathOverflow etiquette by responding to a question 2 years after it has been asked, but your question is answered in the following preprint of mine that just hit the arXiv: <http://arxiv.org/abs/1408.5176>


The preprint shows that any vertex-minimal counterexample to the Erdős--Gallai--Tuza Conjecture has minimum degree greater than n/2; in particular, such graphs are triangular. Thus, the "triangular" version and the unrestricted version are equivalent.


The proof is not difficult, but (at the risk of flattering myself) I don't think it is entirely trivial either.


