  A path in an edge-colored graph is rainbow if no two edges of it are colored
the same, and the graph is rainbow-connected if there is a rainbow path between
each pair of its vertices. The minimum number of colors needed to
rainbow-connect a graph $G$ is the rainbow connection number of $G$, denoted by
$\text{rc}(G)$.
  A simple way to rainbow-connect a graph $G$ is to color the edges of a
spanning tree with distinct colors and then re-use any of these colors to color
the remaining edges of $G$. This proves that $\text{rc}(G) \le |V(G)|-1$. We
ask whether there is a stronger connection between tree-like structures and
rainbow coloring than that is implied by the above trivial argument. For
instance, is it possible to find an upper bound of $t(G) -1$ for
$\text{rc}(G)$, where $t(G)$ is the number of vertices in the largest induced
tree of $G$? The answer turns out to be negative, as there are counter-examples
that show that even $c\cdot t(G)$ is not an upper bound for $\text{rc}(G))$ for
any given constant $c$.
  In this work we show that if we consider the forest number $f(G)$, the number
of vertices in a maximum induced forest of $G$, instead of $t(G)$, then
surprisingly we do get an upper bound. More specifically, we prove that
$\text{rc}(G) \leq f(G) + 2$. Our result indicates a stronger connection
between rainbow connection and tree-like structures than that was suggested by
the simple spanning tree based upper bound.
