---

Claim. Genghua Fan, On diameter 2-critical graphs, Discrete Math. 67 (1987), no. 3, 235--240, doi:10.1016/0012-365X(87)90174-9 (the issue of December 1987 in the Crossref record, the month in this page's name with a nominal day). A graph is diameter 2-critical when it has diameter $2$ and deleting any edge increases its diameter, the graphs of Problem 742. Part (ii) of the paper's Theorem (p. 239) proves that such a graph on $n$ vertices with $e$ edges has $e\le[\frac14n^2]$ for $n\le24$, and the Remark inside its proof (p. 240) gets the same bound for $n=26$ from the paper's inequality (7), $(80n-144)e\le\frac{81}4(n-1)^2n$. Fan says that in both cases only the first part of the conjecture, the inequality, is proved, not its equality clause. The statement is paged at Fan's Theorem. Füredi attests the result ([Fu92] preprint p. 1).

Covers. The inequality the site asks, for $n\le24$ and $n=26$; the equality clause and every other $n$ are not covered (part (iii) bounds $e$ for $n\ge25$ and settles no case).

Depends on. Nothing in this wiki.

Acceptance. Refereed: Discrete Mathematics 67 (1987), no. 3. The site's page does not mention Fan, so no reviewed evidence exists. The formal-conjectures statement file states this result as fan_bound, with no formal proof; it is a statement, not a formalization link.