1
$\begingroup$

Any edge of a tree is a bridge. What is the minimum number of edges that I will need to add so that there are no more bridges in a tree? I have seen the solution from the internet the answer is $\frac{|V|}{2}$, where $|V|$ is the number of vertices in the tree. How can I prove it?

$\endgroup$
  • 3
    $\begingroup$ The minimum number is one: if your tree is a path, you can "unbridge" every edge by adding an edge between the two endpoints. So I guess you're asking for something like this. Let $b(G)$ be the minimum number of edges that can be added to $G$ to give a bridgeless graph. I've heard that, for all trees, $T$, $b(T)\leq |V(T)|/2$ -- how can I prove this? $\endgroup$ – David Richerby Oct 8 '17 at 10:15
  • $\begingroup$ @DavidRicherby the OP assumes an arbitrary tree which can also be a star-like tree, not necessary a path. So, in this case we cannot get away with a single edge. In fact it asks for a minimum number of edges (to add) that would guarantee a bridgeless graph for any tree. $\endgroup$ – fade2black Oct 8 '17 at 10:24
  • 2
    $\begingroup$ @fade2black I understand that, thanks, and I think it's what Redwaul wants to ask. But what they actually ask is "what is the minimum number of edges"? And the answer to the question, as asked, is "one". I'm trying to improve the question so it unambiguously asks what it's supposed to be asking. $\endgroup$ – David Richerby Oct 8 '17 at 10:27
  • $\begingroup$ I do not know the proof but the answer is not no_of_vertices/2. It is (no_of_leaf_nodes + 1) / 2. $\endgroup$ – Ovishek Paul Apr 21 '18 at 9:24
  • $\begingroup$ The correct answer is, as @OvishekPaul said, the ceiling of the half of number of leaves in the tree. Please check here for a proof. $\endgroup$ – Apass.Jack Apr 23 at 17:23
3
$\begingroup$

Let me describe the following algorithm. The basic idea is to add edges such that for any pair of vertices $v_i$ and $v_j$ there is at least two different simple paths between $v_i$ and $v_j$.

  1. Initially all edges are unmarked
  2. Select a simple path $v_i\dots v_j$ containing at least two unmarked edges such as $(v_i,v_j) \notin E$ (vertices $v_i$ and $v_j$ are not connected). If there is no path containing two unmarked edges, then select a path containing one unmarked edge (this means we are done)
  3. Connect $v_i$ and $v_j$ (thereby creating a cycle).
  4. Mark all edges of the (newly created) cycle $v_i\dots v_j$
  5. If there is unmarked edge then go to step 2
  6. Halt

Claim 1: The algorithm adds at most $\frac{|V|}{2}$ edges.
Proof: At step 2 we select a path whose length is at least $2$ (i.e. has at least two edges) containing at least two unmarked edges. Such path exists as long as we have two unmarked edges since there is always a simple path between any two vertices $v_i$ and $v_j$ in a connected tree. So, at each step 2 we decrease the number of unmarked edges by $2$. Since the tree initially has $|V|-1$ unmarked edges, the algorithm adds at most $\big\lceil{\frac{|V|-1}{2}}\big\rceil$ edges. But $\big\lceil{\frac{|V|-1}{2}}\big\rceil \leq \big\lfloor\frac{|V|}{2}\big\rfloor \leq \frac{|V|}{2}$.

Claim 2: The resulting graph created by the algorithm has no bridges.
Proof: Consider a partition $(V',V- V')$. Let $v_i \in V'$ and $v_j \in V-V'$ such that $(v_i, v_j)$ is an edge of the initial tree. Such edge obviously exists since the tree is connected. At some point the algorithm selects a path containing the edge $(v_i, v_j)$ and creates a simple cycle which includes the edge $(v_i, v_j)$. So, there are two different paths between vertices $v_i$ and $v_j$, and hence there are at least two paths (or edges) connecting the partitions $V'$ and $V-V'$.


This algorithm does not compute the optimal number of edges for all possible input instances. For example for a tree which is a path it is enough to add a single edge connecting two end points to transform the tree into a bridgeless graph. My goal is to establish the least upper bound for the number of edges required to add to a tree to transform it into a bridgless graph. For example a star-like tree with even number of vertices is a worst case in which case we need exactly $\frac{|V|}{2}$ edges.

$\endgroup$
  • $\begingroup$ +1, but I think you should mention the star example from your comment to show that there are at least some instances for which your algorithm is optimal. (David Richerby's example of a path shows that your algorithm can be far from optimal on some instances -- it could choose the "middle" two edges, and then the pair of edges flanking those, and so on, adding $|V|/2$ edges when 1 would suffice.) $\endgroup$ – j_random_hacker Oct 8 '17 at 12:45
  • $\begingroup$ @j_random_hacker thanks. Actually I mention about it at the end of my post. In fact my purpose was to answer the question which asks for the minimum number of edges for any tree. By giving the algorithm I just wanted to establish the number of edges needed to add in the worst case (for example if input is a star-like tree). Of course this algorithm by does not provide the optimum output in all cases. That said, I will update my post accordingly to avoid confusion. $\endgroup$ – fade2black Oct 8 '17 at 13:22
  • 1
    $\begingroup$ @j_random_hacker Better now? Please see the footnote. $\endgroup$ – fade2black Oct 8 '17 at 13:32
  • $\begingroup$ Better now. :) (Pad, pad.) $\endgroup$ – j_random_hacker Oct 8 '17 at 13:53
  • $\begingroup$ Here is the optimal answer. The number of edges needed is $\left\lceil \frac {|V|}2\right\rceil$. Please check here for a proof. $\endgroup$ – Apass.Jack Apr 23 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.