Rainbow connectivity of randomly perturbed graphs

In this note we examine the following random graph model: for an arbitrary graph $H$, with quadratic many edges, construct a graph $G$ by randomly adding $m$ edges to $H$ and randomly coloring the edges of $G$ with $r$ colors. We show that for $m$ a large enough constant and $r\ge 5$, every pair of vertices in $G$ are joined by a rainbow path, that is, $G$ is rainbow connected, with high probability. This confirms a conjecture of Anastos and Frieze, who proved the statement for $r\ge 7$ and resolved the case when $r\le 4$ and $m$ is a function of $n$.