Murty-Simon Conjecture

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 . Das and Fox (2026) proved the bound for every , with equality precisely for the balanced complete bipartite graphs , where is the ceiling function. Das and Fox (2026) report that GPT-5.6 Sol found the proof of the bound, which they simplified, and that they supplied the equality characterization.

This is problem 742 in the Erdős problems collection (Bloom 2026).