On diameter 2-critical graphs (Q1096642)

A graph G is diameter 2-critical if \(diam(G)=2\) and \(diam(G-e)>2\) for any its edge e. The reviewer and Simon and Murty conjectured that if G has n vertices and m edges then \(m\leq n^ 2/4\). In this paper it is proved the conjecture for \(n\leq 24\) and also bound \(m<0.2532n^ 2\) for \(n\geq 25\). [Reviewer's remark: Recently Z. Füredi proved the conjecture for very big n.]