---

Füredi and Seress, Maximal triangle-free graphs with restrictions on the degrees, J. Graph Theory 18 (1994), no. 1, 11--24, DOI 10.1002/jgt.3190180103 (Crossref record read; the issue is dated January 1994, and the page name carries the first of that month; card).

The result. Section 6 defines $D_2(n)$ as the least maximum degree of a triangle-free graph of diameter $2$ on $n$ vertices, which is the problem's $f(n)$. Theorem 6.1 states that

$$D_2(n)\le\frac{2}{\sqrt3}\left(\sqrt n+n^{7/24}\right)$$

for all $n>n_0$. The construction takes the largest prime $q$ with $3q^2+2q\le n$, uses the paper's Example 2.2, and distributes the remaining $r=n-3q^2-2q<2q^{19/12}$ vertices over the classes so that each vertex of the core on $2(q^2+q)$ vertices has degree at most $2q-1+2\lceil r/q\rceil$, while every vertex of a class has degree $2(q+1)$ (Example 2.2). With the trivial bound $f(n)\ge\sqrt{n-1}$ (a graph of diameter $2$ with every degree at most $d$ has at most $d^2+1$ vertices), this gives $\sqrt{n-1}\le f(n)\le(2/\sqrt3+o(1))\sqrt n$ for all large $n$: the order of growth of $f(n)$ is $\sqrt n$, and $f(n)/\sqrt n$ does not tend to infinity. The site's commentary states this bound; it is the smallest upper constant among the sources read, and the remark in Alon's note of 2 July 2024 calls it a better upper estimate than Hanson and Seyffarth's. Section 6 cites the earlier bound of Hanson and Seyffarth, which it reports as $(2+o(1))\sqrt n$ and improves. The value of $\lim f(n)/\sqrt n$, if it exists, lies in $[1,2/\sqrt3]$ and is not determined by any source read; the problem does not ask for it.

Depends on. Nothing in this wiki.

Acceptance. Refereed publication in the Journal of Graph Theory, cited with its venue above. The site's curator, Thomas Bloom, marks the problem DISPROVED and credits the bound to Füredi and Seress under the reference [FuSe94] in the commentary; that credit is the reviewed evidence, and Bloom took no part in the paper. No independent review of the argument was made here, and no proof step was checked beyond the statement and the construction's description.