Minimum number of edges to add such that there are no bridges on a tree
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$. 


Initially all edges are unmarked    
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) 
Connect $v_i$ and $v_j$ (thereby creating a cycle). 
Mark all edges of the (newly created) cycle $v_i\dots v_j$
If there is unmarked edge then go to step 2
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.