Erdős Problem #1034

Let \(G\) be a graph on \(n\) vertices with \(>n^2/4\) many edges. Must there be a triangle \(T\) in \(G\) and vertices \(y_1,\ldots,y_t\), where \(t>(\frac{1}{2}-o(1))n\), such that every \(y_i\) is joined to at least two vertices of \(T\)? A conjecture of Erdős and Faudree; a stronger version of [905]. This has been solved in the negative by Ma and Tang [MaTa25], who construct a graph with \(n\) vertices and \(>n^2/4\) edges in which every triangle has at most \((2-(5/2)^{1/2}+o(1))n\) vertices adjacent to at least two of its vertices (note that \(2-(5/2)^{1/2}\approx 0.4189\)).