Problem 134

Let $\epsilon,\delta>0$ and $n$ be sufficiently large in terms of $\epsilon$ and $\delta$ . Let $G$ be a triangle-free graph on $n$ vertices with maximum degree $<n^{1/2-\epsilon}$ .

Can $G$ be made into a triangle-free graph with diameter $2$ by adding at most $\delta n^2$ edges?

Source: erdosproblems.com/134

Graph theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

PROVED (LEAN). Alon's published Theorem 3.2 gives a stronger quantitative bound and implies the exact fixed- $\epsilon$ , fixed- $\delta$ question as explained below; the site's curator credits Alon's note with the solution (claim page (Alon, 2024)). The site's label carries a Lean suffix for the Aristotle formalization of Alon's theorem reported on the thread, which is linked from the claim page and is not built or audited here. Search scope, 2026-10-07: the site's commentary and thread.

Al26: Noga Alon, Problems and Results in Extremal Combinatorics–V. In Sum(m)it280, Bolyai Society Mathematical Studies 32, Springer (2026), 13–29. DOI.
EGR98: Erdős, P., Gyárfás, A. and Ruszinkó, M., How to decrease the diameter of triangle-free graphs. Combinatorica 18 (1998), no. 4, 493-501, DOI 10.1007/s004930050035. Library home: Erdős, Gyárfás and Ruszinkó 1998.
Er97b: Erdős, Paul, Some old and new problems in various branches of combinatorics. Discrete Math. 165/166 (1997), 227-231; item 7, pp. 229-230. Library home: Erdős 1997.

Problem 134

Status

Proof claims

Discussion