Rainbow connection and minimum degree

An edge-coloured graph GG is rainbow connected if any two vertices are connected by a path whose edges have distinct colours. The rainbow connection number   of a connected graph GG, denoted rc(G)rc(G), is the smallest number of colours that are needed in order to make GG rainbow connected. Krivelevich and Yuster (2010) [5] have shown that a connected graph GG with nn vertices has rc(G)<20nδ(G). In this paper we prove that a connected graph GG with nn vertices has rc(G)<4nδ(G)+1+4.