It appears plausible to me that if we have a connected graph $G$ with diameter $d$ and we remove a non-cut edge $e$ from it, the diameter of the resulting graph $G_e$ will be at most $2d$.
By removing a non-cut edge I mean that the resulting graph is still connected.
I was not able to find a proof or a counter-example.
Any suggestion?
Thanks.
EDIT:
I've tried to follow Perce's hint, and I'm quite sure I success in showing what I was looking for, but it was hard for me to explain. Then I ask for the correctness of my proof.
Let $G$ be a graph with a certain diameter $d$, and let $$(u_0,u_d)=<u_0, u_1, …, u_i, …, u_d > (0\leq i \leq d)$$ a shortest path from some node $u_0$ to some node $u_d$ such that its lenght is $d$. Let's add to $G$ an edge $e$.
By adding $e$, maybe, there will be a shorter path $(u_0,u_d)'$ in the graph from $u_0$ to $u_d$ that differs from $(u_0,u_d)$ for some nodes $u_i$ (with $0<i<d$ ); it's easy to see that these different nodes are consecutive in $(u_0,u_d)'$, that is they replace a substring of $<u_0, u_1, …, u_i, …, u_d >$.
Indeed, they form a new shortest path between some $u_j$ and $u_k$ using the new edge $e$ (because this new path $(u_j,u_k)$ wasn't the shortest before adding $e$); if there were not-consecutive $u_i$s in $(u_0,u_d)'$, then $e$ would be used more than one time, and $(u_0,u_d)'$ would not be a shortest path.
EDIT2: fixed the following part of my solution
Hence, adding an edge we create at most one shorter route among the nodes in the path $(u_0,u_d)$, that in the best case is of lenght 1 (if we use $e$ itself).
Now, it's easy to see that, by adding a an edge between two nodes in a path, we cannot reduce its lenght $l$ below $l/2$.
Best Answer
Let $G$ be a connected graph with diameter $D$, and let $v$ be a vertex that is part of a diametric pair. Now define $S_i$ to be the vertices at distance $i$ from $u$. By construction, $S_i$ is not empty for $0\le i\le D$.
Now contract the $S_i$ and discard loops and multiple edges to get a graph $H$ on $D+1$ vertices $s_0, s_1,\ldots, s_D$.
Fact 1: $H$ is a path.
Proof: Build the $S_i$ via breadth-first search, which shows there is an edge between $s_i$ and $s_{i+1}$. On the other hand, shortcuts contradict the definition of $S_i$.
Now add a new edge $ij$ to $G$ to get a graph $G'$. Contract the same sets of vertices $S_i$ that were contracted to make $H$ and again discard multiple edges to get $H'$.
Fact 2: $H'$ is a path plus one edge.
Proof: The surviving edges are just the edges of $H$ plus the new edge $ij$.
Fact 3: The diameter of $H'$ is at most the diameter of $G'$.
Proof: Contracting shortens paths and discarding multiple edges leaves distances the same.
Thus if the diameter of $H'$ is at least $D/2$, then so is the diameter of $G'$, and we are done.
Edit: Pedro is right that there was a bug in my original argument for the path case. Here is a quick patch that still uses the structure of a BFS.
$H'$ has the structure of a cycle, possibly with up to two "tails" ending at $s_0$ or $s_D$; these tails meet the cycle at neighboring vertices. For zero tails, the claim is clear. For one tail, do a BFS from the end of the tail. The BFS goes one vertex per layer, splits, and then merges, so each BFS layer has at most two vertices. Again we are done.
Now look at two tails, with $a$ and $b$ non cycle vertices in each (ie the length of the tail) and $a\le b$. Consider the BFS starting at end of the longer tail. This time, each layer has one vertex for $b$ steps, the BFS branches in a layer of two vertices, and then there are three vertices per layer for at most $a$ steps more. Since $b\ge a$, we charge the layers with three vertices to layers with one vertex, so we are done.