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)=<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$.

$\endgroup$
17
  • 4
    $\begingroup$ Hint: Suppose u and v are two vertices in $G_e$ attaining the distance $diam(G_e)$. Let $N_i$ be the $i^{th}$ neighborhood of u. Now add e to connect a vertex in $N_i$ to a vertex in $N_j$. Can you find two vertices whose distance is still at least $diam(G_e)/2$? $\endgroup$
    – Perce
    Commented Dec 20, 2011 at 5:41
  • 1
    $\begingroup$ I had a proof, but it's kind of ugly since it is done through case-by-case analysis. If there is no one posting the answer, I will post my answer. $\endgroup$
    – Paul
    Commented Dec 20, 2011 at 13:41
  • 1
    $\begingroup$ Two comments: First, in your proof, you said, "By adding $e$, maybe, there will be a shorter path..." In fact, you need to show that there must exist such a path to reduce the diameter. Second, you not only need to show that the distance between the vertices which has distance $d$ in $G-e$ reduces to $d/2$ in $G$, but also show that the distance of all vertices which has distance greater than $d/2$ in $G-e$ can be reduces to $d/2$ in $G$. $\endgroup$
    – Paul
    Commented Dec 22, 2011 at 7:25
  • 1
    $\begingroup$ @Emanuele Natale The $i^{th}$ neighborhood of $u$ is the set of vertices at distance $i$ from $u$. It is not sufficient to consider a single path $u_0,u_1,...,u_d$. Instead we consider all paths simultaneously, i.e. the sequence $u=N_0, N_1, ..., N_d$. $\endgroup$
    – Perce
    Commented Dec 23, 2011 at 21:55
  • 1
    $\begingroup$ @EmanueleNatale: The problem in your argument is that you can't just look at a specific long path in $G_e$ and then argue it can't get too short. This isn't even true, as can be seen when $G_e$ is a path and you connect the two ends. $\endgroup$
    – Louis
    Commented Dec 24, 2011 at 10:08

2 Answers 2

Reset to default
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I'm sorry there's no possibility to accept multiple answers, since Pedro's answer continues your, but it's more clear to me than your patching. By the way, a misprint: you say that $a$ and $b$ are non cycle vertices and $a\leq b$, considering $a$ and $b$ both vertices and numbers. $\endgroup$
    – Immanuel Weihnachten
    Commented Dec 25, 2011 at 16:51
  • $\begingroup$ 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. $\endgroup$
    – Louis
    Commented Dec 25, 2011 at 17:08
4
+50
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ You are too nice. I had a bug in the argument for the path, which I patched up along the same lines. Nice. $\endgroup$
    – Louis
    Commented Dec 25, 2011 at 0:57
  • $\begingroup$ @Pedro, maybe a little mistpint: you say "let $u_j$ be the vertex of the cycle where the path with $j$ edges begins", and after you use $u_i,w_i,v_i$, but in your inequality about distances is clear you're referring to $u_j$, not $u_i$ that would be the vertex of the cycle where the path with $i$ edges begins. $\endgroup$
    – Immanuel Weihnachten
    Commented Dec 25, 2011 at 16:36
  • $\begingroup$ @EmanueleNatale: Thanks, you're absolutely correct. $\endgroup$
    – Pedro M.
    Commented Dec 25, 2011 at 17:04
  • 2
    $\begingroup$ 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. $\endgroup$
    – GeoffDS
    Commented Dec 26, 2011 at 4:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .