The Murty-Simon conjecture asserts that a simple graph 
on 
vertices with graph
diameter 2, such that deleting any graph edge increases
its graph diameter, has at most 
edges (Füredi 1992).
Here 
is the floor function, and disconnection after
deletion is regarded as increasing the graph diameter
to infinity.
Balanced complete bipartite graphs attain the bound whenever their two parts are nonempty and the graph
diameter is 2. Füredi (1992) proved the conjectured bound for sufficiently
large 
;
the unrestricted conjecture remains open.
This is problem 742 in the Erdős problems collection (Bloom 2026).
