Diameter increase caused by edge deletion

We consider the following problem: Given positive integers k and D , what is the maximum diameter of the graph obtained by deleting k edges from a graph G with diameter D , assuming that the resulting graph is still connected? For undirected graphs G we prove an upper bound of ( k + 1) D and a lower bound of ( k + 1) D − k for even D and of ( k + 1) D − 2 k + 2 for odd D ⩾ 3. For the special cases of k = 2 and k = 3, we derive the exact bounds of 3 D − 1 and 4 D − 2, respectively. For D = 2 we prove exact bounds of k + 2 and k + 3, for k ⩽ 4 and k = 6, and k = 5 and k ⩾ 7, respectively. For the special case of D = 1 we derive an exact bound on the resulting maximum diameter of order θ(√ k ). For directed graphs G , the bounds depend strongly on D : for D = 1 and D = 2 we derive exact bounds of θ(√ k ) and of 2 k + 2, respectively, while for D ⩾ 3 the resulting diameter is in general unbounded in terms of k and D . Finally, we prove several related problems NP‐complete.