Sufficient conditions for 2-rainbow connected graphs

An edge-coloured connected graph GG is rainbow connected if each two vertices are connected by a path whose edges have distinct colours. If such a colouring uses kk colours then GG is called kk-rainbow connected. The rainbow connection number of GG, denoted by rc(G), is the minimum kk such that GG is kk-rainbow connected. Even the problem to decide whether rc(G)=2 is NP-complete. It has been shown that if GG is a connected graph of order nn and size mm with n−22+2≤m≤n−12, then 2≤rc(G)≤3.In this paper we will present sufficient conditions for graphs GG of this size to fulfil rc(G)=2 depending on vertex degrees.