Diameter of a graph when removing a non-cut edge

Solution 1:

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.

Solution 2:

I unfortunately still can't comment, but this refers to Louis's answer below:

Louis, I don't see why the combinatorial structure of H' implies that each layer has at most two vertices. Suppose G is just a path $(u_0, u_1, u_2,u_3,u_4,u_5)$. Then $H = G$. Now let us add the edge $[u_0,u_4]$ to get $G'$. Now $H' = G'$ and the layers are:

Distance $1$ from $u_0$: $u_1,u_4$

Distance $2$ from $u_0$: $u_2,u_3,u_5$, which has three vertices.

In fact there is no vertex with distance $\geq 3$ from $u_0$, but $dist(u_2,u_5) = 3$.

EDIT: I believe this completes Louis's proof in a satisfactory manner:

We need to show that the diameter of $H'$ is at least $D/2$. Now from the construction it is clear that there are three possibilities for $H'$: it is either

(a) a cycle with $D+1$ edges; (b) a cycle with $D+1-i$ edges plus a path with $i$ edges starting at one of the vertices; (c) a cycle with $D+1-i-j$ edges plus two paths, with $i$ and $j$ edges respectively, starting at adjacent vertices in the cycle.

(a) and (b) clearly have diameter $\geq D/2$. For (c), suppose $i \leq j$ and let $u_j$ be the vertex of the cycle where the path with $j$ edges begins, and $v_j$ the respective endpoint. There exists $w_j$ in the cycle such that $dist(u_j,w_j) \geq \frac{D-i-j}{2}$. Therefore $$dist(w_j,v_j) = dist(w_j,u_j) + dist(u_j,v_j) \geq \frac{D + j - i}{2} \geq \frac{D}{2},$$

which completes the proof.