In this section, \(G\)  will be a connected graph with \(n\)  vertices, \(m\)  edges, diameter \(d\) , radius \(r\)  and \(b\)  bridges. Let \(G^{\prime }\)  be the graph obtained by contracting every bridge of \(G\) . The diameter (radius) of \(G^{\prime }\)  is at most \(d\)  (\(r\) ). We can extend a rainbow colouring of \(G^{\prime }\)  to \(G\)  by giving a new colour to every bridge of \(G\) . Hence \(rc(G) \le rc(G^{\prime }) + b\) . We can find all the bridges in a connected graph in \(O(m)\)  time [1]}. Now, using the algorithm in Section REF  to colour \(G^{\prime }\) , we can colour \(G\)  using at most \(r(r+2) + b\)  colours in \(O(nm)\)  time. Since \(r(r+2) + b \le \max \lbrace r, b\rbrace (r+3)\)  and since \(\max \lbrace r,b\rbrace \)  is a lower bound on \(rc(G)\) , we immediately have a \((r+3)\) -factor \(O(nm)\)  approximation algorithm to rainbow colour any connected graph.
