Minimally extend a tree such that there are no bridges in the new graph We are given an undirected tree on which we should add the minimum number of edges such that there are no bridges in the new graph.

An edge $e$ is a bridge if the graph with that edge removed is no longer connected.

For example, here is a tree with 8 nodes

1 2
2 3
3 4
4 5
3 6
3 7
3 8
At least three edges should be added. For example: (1, 6), (5, 7), (8,4)




In very small graphs we can brute force all possible new edges. However, this is too slow for bigger trees. I tried making some observations but I couldn't find anything that could solve the problem.

This problem is the task "NET" from Baltic Olympiad in Informatics 2015.
Start by proving the following statement:

Let $G=(V,E)$ be an undirected graph. There are no $\mathrm{bridges}$ if and only if there are two edge disjoint spanning trees of $G$.

Proof:

Suppose there are two edge disjoint spanning trees, $T_1, T_2$ of $G$.
Now we remove an arbitrary edge. If it belongs to neither $T_1$, or $T_2$, we're done. If it belongs to $T_1$, it is therefore not in $T_2 $ (symmetrical for $T_2$)  $\Rightarrow$ $G$ is still connected $\Rightarrow$ there are no $\mathrm{bridges}$ in $G$.

Suppose there are no two edge disjoint spanning trees. Then there is at least one cut $C^*$ of $G$ s.t $C^*=\{A, \bar{A}\}$ and $\delta(C^*) \leq 1$. Otherwise it is easy to constructively show there are two spanning trees.
Let $e$ denote the edge between $A$ and $\bar{A}$. Since $e$ is the only edge connecting the two subsets, by removing it, $G$ is separated into two unconnected componenets, therefore $e$ is a $\mathrm{bridge}$



If you can add any edge you want, simply extend $G$ s.t there are two edge disjoint spanning trees. If you start from a tree, it means you have exactly $n-1$ edges, and to create another distinct spanning tree you would have at least $n-1$ additional edges.
If you can't add any edge you want, see http://i.stanford.edu/pub/cstr/reports/cs/tr/74/455/CS-TR-74-455.pdf by Tarjan on disjoint spanning trees (with algorithm)