  A path in an edge colored graph is said to be a rainbow path if no two edges
on the path have the same color. An edge colored graph is (strongly) rainbow
connected if there exists a (geodesic) rainbow path between every pair of
vertices. The (strong) rainbow connectivity of a graph $G$, denoted by
($src(G)$, respectively) $rc(G)$ is the smallest number of colors required to
edge color the graph such that the graph is (strong) rainbow connected. It is
known that for \emph{even} $k$ to decide whether the rainbow connectivity of a
graph is at most $k$ or not is NP-hard. It was conjectured that for all $k$, to
decide whether $rc(G) \leq k$ is NP-hard. In this paper we prove this
conjecture. We also show that it is NP-hard to decide whether $src(G) \leq k$
or not even when $G$ is a bipartite graph.
