A conjecture of Erdős and Faudree; a stronger version of [905].

Erdős [Er93] says 'perhaps this conjecture is a bit too optimistic', and in general asks how large $t$ can be, and suggested the answer is different if $G$ has no $K_4$.

This has been solved in the negative by Ma and Tang (see their note here, and also the comments), 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$).

In general, Erdős and Faudree asked about the threshold $h(n)$ such that every graph with $n$ vertices and $>n^2/4$ edges contained a triangle and $h(n)$ other vertices which are connected to at least two vertices of the triangle. The above contruction of Ma and Tang, combined with the fact that every graph with $>n^2/4$ edges contains a book of size $n/6$, shows that\[(1/6-o(1))n \leq h(n) \leq (2-(5/2)^{1/2}+o(1))n.\]In the comments Ma and Tang sketch a proof that the conjecture remains false even if we assume that $G$ contains no $K_4$, constructing a graph with $n$ vertices, $>n^2/4$ edges, and no $K_4$, in which every triangle has at most\[(2\sqrt{3}-3+o(1))n\]vertices adjacent to at least two of its vertices (note that $2\sqrt{3}-3\approx 0.464$).

View the LaTeX source

This page was last edited 28 October 2025.

5 comments on this problem