Problem 742

Let $G$ be a graph on $n$ vertices with diameter $2$ , such that deleting any edge increases the diameter of $G$ . Is it true that $G$ has at most $n^2/4$ edges?

Source: erdosproblems.com/742

Graph theory

Wiki page

Status

ClaimedProved

A full solution has been claimed but not yet accepted. The statement is true.

DECIDABLE is the site's label; it describes the shape of what remains and is not a theorem. The standing in the frontmatter is derived from the claim pages: Füredi's large- $n$ theorem is the accepted partial claim Füredi 1988/1992 (the reduction to a finite check), and the proof claim for all $n$ on the site's proof-claim tab is the pending full claim jstar 2026, unreviewed. The derived standing, claimed and proved, departs from the label because that full claim is pending; the label matches Füredi's accepted reduction alone. Proved for all sufficiently large $n$ : Füredi's Theorem 1.2 [Fu92] (J. Graph Theory 16 (1992), 81--98, refereed; locators from the 1988 preprint) states that Conjecture 1.1, the bound with its equality clause, is true for $n>n_0$ , where "The value of $n_0$ is explicitly computable, but the proof given here yields a vastly huge number (a tower of 2's of height about 1000)". The finite remainder $n\le n_0$ has no stated extent; its checked part is Fan's verification for $n\le24$ and $n=26$ , the accepted partial claim Fan 1987, Fan's Theorem (ii) with its Remark [Fa87] (Discrete Math. 67 (1987), refereed), which proves the inequality and not the equality clause for those $n$ , as Füredi attests it; and for every $n$ Füredi's paper proves $|E(G)|\le(1+o(1))n^2/4$ , its Corollary 3.6. The site's proof-claim tab carries one full proof claim for all $n$ , unreviewed, recorded on its claim page and below; the site's label is unchanged and no accepted proof for all $n$ was found in the search whose scope the Current assessment records. Whether the label should stand for a statement proved for all $n>n_0$ with $n_0$ astronomically large and unchecked for finitely many $n$ is a question of the catalog's labeling that this page records and does not decide.

Fu92: Füredi, Zoltán, The maximum number of edges in a minimal graph of diameter $2$ . J. Graph Theory 16 (1992), no. 1, 81--98, doi:10.1002/jgt.3190160110 (March 1992; Crossref record). Locators are the pages of IMA Preprint Series #408 (March 1988): Conjecture 1.1 and the earlier bounds, preprint p. 1; Theorem 1.2 and the remark on $n_0$ , p. 2; Section 5, pp. 11--12. The journal text is not held and was not compared. Library home: Füredi 1992; paged at Füredi 1992, Theorem 1.2 (preprint p. 2).
CaHa79: Caccetta, Louis and Häggkvist, Roland, On diameter critical graphs. Discrete Math. 28 (1979), no. 3, 223--229, doi:10.1016/0012-365X(79)90129-8 (Crossref record, 2026-09-19, with the publisher's open-archive license dated 2013; 7 pages): Conjecture 1, headed "(Simon and Murty)", with its equality clause, p. 223; Theorem 1, $\varepsilon<\bigl(\frac{1+\sqrt5}{12}\bigr)\nu^2<0.27\nu^2$ , with its proof, p. 228; the reference "[2] U.S.R. Murty, Private communication" and the acknowledgement to Murty, p. 229. Plesník is not named in the paper. Library home: Caccetta and Häggkvist 1979; paged at Caccetta and Häggkvist 1979, Conjecture 1 (Simon and Murty) and Caccetta and Häggkvist 1979, Theorem 1.
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), no. 1, 25--42, doi:10.1007/BF02579174 (Crossref record); p. 15 of the retyped copy, which has its own pagination, with the reference [67] on p. 20. Library home: Erdős 1981.
Pl75: Plesník, J., Critical graphs of given diameter. Acta Fac. Rerum Natur. Univ. Comenian. Math. 30 (1975), 71--93, as [Fu92] cites it. Not held. Its bound $|E|<3n(n-1)/8$ is known from [Fu92] p. 1 and from [Fa87] p. 235, which cites it as Theorem 13 of the paper.
Fa87: Fan, Genghua, On diameter $2$ -critical graphs. Discrete Math. 67 (1987), 235--240, doi:10.1016/0012-365X(87)90174-9 (the publisher's DOI; the paper carries no issue number on its printed head; 6 pages): the Conjecture, credited to Simon and Murty "(see [1])" after Plesník's observation, with the account of the earlier bounds and of the wrong 1984 proof, p. 235; the Theorem, (ii) $e\le[\frac14n^2]$ for $n\le24$ and (iii) $e<\frac14n^2+(n^2-16.2\,n+56)/320$ for $n\ge25$ , p. 239; the Remark that inequality (7) also gives $e\le[\frac14n^2]$ for $n=26$ , and that both cases prove "only" the first part of the conjecture, p. 240. Library home: Fan 1987; paged at Fan 1987, Theorem (§ 5).
Xu84: Xu, J. M., Proof of a conjecture of Simon and Murty (Chinese). J. Math. Res. Exposition 4 (1984), 85--86; corrigendum ibid. 5 (1985), 38, as [Fu92] cites it ("An incorrect proof was published [X] in 1984"). Not held. [Fa87] p. 235 also states that the "proof" is wrong, because "the method used in [3] is the same as that used in [2], which cannot prove the conjecture"; Fan's reference lists no corrigendum.

Problem 742

Status

Proof claims

Discussion