Erdős Problem 742

Murty-Simon Conjecture*

Let $G$ be a graph on $n$ vertices with diameter $2$ such that deleting any edge increases the diameter. Is it true that $G$ has at most $\lfloor n^2 / 4 \rfloor$ edges? Equality is conjectured to hold for the complete balanced bipartite graph $K_{\lceil n/2 \rceil, \lfloor n/2 \rfloor}$.

The conjecture is resolved up to a finite check: Fan [Fa87] verified it for $n \leq 24$ and $n = 26$, and Füredi [Fü92] proved it for all sufficiently large $n$.