Problem 133

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$ ?

Second statement

Let $f(n)$ be maximal 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$ ?

Source: erdosproblems.com/133

Graph theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved. The site's label answers the second question: Erdős and Pach conjectured $f(n)/\sqrt n\to\infty$ , and $f(n)$ has order exactly $\sqrt n$ . 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) is matched by Cayley graphs on symmetric complete sum-free sets: Hanson and Seyffarth [HaSe84] gave $f(n)=O(\sqrt n)$ , a bound that the site, Füredi and Seress and Alon state for all large $n$ and Haviv and Levy for the sequence $n=m^2+5m+2$ (claim page (Hanson and Seyffarth, 1984), partial), and Haviv and Levy [HaLe18] constructed such sets in every large cyclic group, proving $f(n)=O(\sqrt n)$ for every large $n$ (claim page (Haviv and Levy, 2017)). Füredi and Seress's projective-plane construction [FuSe94] gives the best known constant, $f(n)\le(2/\sqrt3+o(1))\sqrt n$ for all large $n$ (claim page (Füredi and Seress, 1994)); the last two are refereed and settle the problem. The constant, between $1$ and $2/\sqrt3$ , is not asked and is open; Alon's 2024 note, also cited on Problem 134, conjectures $f(n)\sim\sqrt n$ , and one unreviewed proof claim of 2026-09-15 on the site's proof-claim tab asserts that the constant is $1$ (claim page (Korsky, 2026)). A Lean development attributed to Hanson and Seyffarth's result is linked from their claim page and is not built here. Search scope, 2026-10-07: the site's commentary, its comment thread (empty) and its proof-claim tab.

Notes

The site's wording takes the least $f(n)$ such that every triangle-free graph of diameter $2$ on $n$ vertices has a vertex of degree at least $f(n)$ . Every value up to the least maximum degree of such a graph has that property, so the least one is $0$ for every $n$ and both questions become trivial. The smallest failing instance is $n=3$ : the only triangle-free graph of diameter $2$ on three vertices is the path, of maximum degree $2$ , while the minimal $f(3)$ is $0$ . The change replaces "minimal" by "maximal"; the largest value with the property is the least possible maximum degree of a triangle-free graph of diameter $2$ on $n$ vertices. The evidence is the poser's own statement of the question: [Er97b] item 7, p. 229, defines $f(n)$ as the smallest integer for which some triangle-free graph on $n$ vertices of diameter two has maximum degree $f(n)$ , and states the Erdős--Pach conjecture $f(n)/n^{1/2}\to\infty$ for that function. Füredi and Seress define their $D_2(n)$ in the same way (Section 6 of [FuSe94], p. 23), and the site's own commentary derives the lower bound $f(n)\ge(1-o(1))\sqrt n$ , which holds only for the corrected $f(n)$ . The defect is the site's; [Er97b] has the right extremum. No result about the site's wording is recorded.

Er97b: Erdős, Paul, Some old and new problems in various branches of combinatorics. Discrete Math. 165/166 (1997), 227--231, DOI 10.1016/S0012-365X(96)00173-2; item 7, p. 229: the definition of $f(n)$ , the Erdős--Pach conjecture $f(n)/n^{1/2}\to\infty$ and Simonovits's Kneser graph with $f(n)<n^{1-c}$ for $n=\binom{3m-1}m$ , which leaves the question open. Library home: Erdős 1997.
FuSe94: Füredi, Zoltán and Seress, Ákos, 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 accessed); Theorem 6.1, Section 6. Library home: Füredi and Seress 1994.
HaLe18: Haviv, Ishay and Levy, Dan, Symmetric complete sum-free sets in cyclic groups. Israel J. Math. 227 (2018), no. 2, 931-956, DOI 10.1007/s11856-018-1754-5 (Crossref record accessed); arXiv:1703.04118; Theorem 1.5 and the Section 1 remark on regular triangle-free graphs of diameter $2$ . Library home: Haviv and Levy 2018.
HaSe84: Hanson, D. and Seyffarth, K., $k$ -saturated graphs of prescribed maximum degree. Congr. Numer. (1984), 169-182; [FuSe94] cites volume 42, pp. 169-182, and [HaLe18] cites volume 44, pp. 127-138.

Problem 133

Second statement

Status

Notes

Proof claims

Discussion