Logo
All Random Solved Random Open
OPEN
Let $f(n)$ be minimal such that every triangle-free graph $G$ with $n$ vertices and diameter $2$ contains a vertex with degree $\geq f(n)$. What is the order of growth of $f(n)$? Does $f(n)/\sqrt{n}\to \infty$?
Asked by Erdős and Pach. Simonovits observed that the subsets of $[3m-1]$ of size $m$, two sets joined by edge if and only if they are disjoint, forms a triangle-free graph of diameter $2$ which is regular of degree $\binom{2m-1}{m}$, showing that $f(n)=o(n)$ infinitely often. This graph may have the minimal possible $f$, but Erdős encourages the reader to try and find a better graph.