A note on the minimum size of -rainbow-connected graphs

An edge-coloured graph G is rainbow-connected if there exists a rainbow path joining any two vertices. A graph G is said to be k -rainbow-connected if there exists an edge-colouring of G with at most k colours that is rainbow-connected. For integers n and k , let t ( n , k ) denote the minimum number of edges in k -rainbow-connected graphs of order n . In this note, we prove that t ( n , k ) = ⌈ k ( n − 2 ) k − 1 ⌉ for n , k ≥ 3 .