13
$\begingroup$

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)= (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 ); it's easy to see that these different nodes are consecutive in (u_0,u_d)', that is they replace a substring of $$. 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$.

  • 1
    See Fact 5 of http://www.cs.clemso$n$.edu/~goddard/papers/graphs/distanceChapter.pdf for this result, as well as one for deleting a vertex that is not a cut vertex.2012-01-18

2 Answers 2

5

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.

  • 0
    You should think about it then, since there wasn't$a$misprint. The idea is just to compare the BFS to$a$process that munches two vertices at a time. In the cycle and one tail case, the BFS never moves faster. In the two tail case, the point is that the BFS from the end of the longer falls behind enough that even when it speeds up, it never overtakes the two at a time process.2011-12-25
4

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.

  • 2
    I awarded you the bounty because you found a vital mistake and fixed it, and also because your reputation was lower at the time. This will bump you up to over 100.2011-12-26