If a tree $T$ becomes bridgeless after edges in a set $S$ have been added to $T$, we will say $S$ doubly connects $T$.
The minimum size of $S$ that doubly connects $T$ is $\lceil n/2\rceil$, where $n$ is the number of the leaves in $T$.
The simple idea is that the edges to be added should only connect leaves of the tree. After we have selected an edge to be added, we can delete its two vertices and some related vertices and edges so that the remaining tree has two less leaves. We will make sure that solving the problem for the remaining tree is enough to solve the original problem.
Outline of an algorithm
Input: A tree $T$ whose vertices are $0, \cdots, n-1$ where $n\ge2$. The set of vertices that are neighbours to vertex $v$ is $N[v]$.
Output: A list of edges whose size is minimum such that $T$ with those edges added is bridgeless.
Helper procedure to delete a vertex $v$ of degree 2: Suppose $x$ and $y$ are the two vertices connected to $v$. Mark $v$ as deleted. Replace $v$ in $N[x]$ with $y$. Replace $v$ in $N[y]$ with $x$. Note that $T$ remains a tree after the procedure.
Helper procedure to delete a leaf: Suppose $v$ is a leaf that is connected to $u$. If $u$ is a leaf, just return. Otherwise, do the following. Mark $v$ as deleted. Delete $v$ from $N[u]$. If the degree of $u$ is 2, apply the procedure above to delete $u$.
Main Procedure:
Delete all vertices of degree 2.
Now each vertex is either a leaf or connected to two or more other vertices.
Let $S$ be an empty list. Loop the following.
- Find a pair of leaves the distance between which is at least 3. Let them be $u$ and $v$. Add edge $(u,v)$ to $S$. Apply the helper procedure to delete $u$ and $v$.
- If no such pair can be found, break the loop.
Now $T$ has no path of length 3 and each vertex of $T$ is either a leaf or connected to two or more other vertices. There are two cases.
- $T$ has only one edge. Let it be $(u,v)$. Add edge $(u,v)$ to $S$. (If we add the edge $(u,v)$ in $S$ to the tree, we will have two edges connecting $u$ and $v$. This is the only place where we introduce a parallel edge.)
- $T$ has three or more edges. $T$ must be a star graph. Let the center vertex be $u$ and other vertices be $v_1, \cdots, v_m$. If $m$ is even, add edges $(v_1, v_2)$, $(v_3, v_4)$, $\cdots$, $(v_{m-1}, v_{m})$ to $S$. If $m$ is odd, add edges $(v_1, v_2)$, $(v_3, v_4)$, $\cdots$, $(v_{m-2}, v_{m-1})$ as well as edge $(v_1, v_m)$ to $S$.
Implementation of the algorithm
There are a few ways to implement step 2.1.
A naive way to find a pair of such leaves is to do a depth first search from any vertex.
In order to find such pair of vertices faster, we can also select any two neighboring internal node $x$ and $y$. The edge $(x,y)$ splits $T$ into two subtress, one part that has $x$ and the other part that has $y$. We can pair any leaf of $T$ in one part with any leaf of $T$ in the other part. We can do this recursively.
Exercises
Exercise 1. If an edge set $S$ doubly connects a tree $T$, then then $|S|\ge\lceil n/2\rceil$. (Hint, each leaf of $T$ must be an endpoint of some edge in $S$.)
Exercise 2. Use the notations in the algorithm. Show the algorithm is correct by verifying the following.
- For an iteration in step 2, let $T_s$ be $T$ at the start of the iteration and $T_e$ be $T$ at the end of the iteration and $e$ be the edge added to $S$. If $B$ doubly connects $T_e$, then $B\cup \{e\}$ doubly connects $T_s$.
- In step 3, edges added in step 3 doubly connects $T$.
- At the end of algorithm, $|S|=\lceil n/2\rceil$.
Exercise 3. Modify the algorithm so that no parallel edge is needed unless $n=2$.