  The $r$-color size-Ramsey number of a graph $H$, denoted $\hat{R}_r(H)$ is
the smallest number of edges in a graph $G$ having the property that every
$r$-coloring of the edges of $G$ contains a monochromatic copy of $H$.
  Krivelevich proved that $\hat{R}_r(P_{m+1})=\Omega(r^2m)$ where $P_{m+1}$ is
the path on $m$ edges. He explains that his proof actually applies to any
connected graph $H$ with $m$ edges and vertex cover number larger than
$\sqrt{m}$. He also notes that some restriction on the vertex cover number is
necessary since the star with $m$ edges, $K_{1,m}$, has vertex cover number 1
and satisfies $\hat{R}_r(K_{1,m})=r(m-1)+1$. We prove that the star is actually
the only exception; that is, $\hat{R}_r(H)=\Omega(r^2m)$ for every non-star
connected graph $H$ with $m$ edges.
  We also prove a strengthening of this result for trees. It follows from
results of Beck and Dellamonica that $\hat{R}_2(T)=\Theta(\beta(T))$ for every
tree $T$ with bipartition $\{V_1, V_2\}$ and $\beta(T)=|V_1|\max\{d(v):v\in
V_1\}+|V_2|\max\{d(v):v\in V_2\}$. We prove that
$\hat{R}_r(T)=\Omega(r^2\beta(T))$ for every tree $T$, again with the exception
of the star. Additionally, we prove that for a certain class of trees
$\mathcal{T}$ (which includes all trees of radius 2 and all non-star trees with
linear maximum degree) we have $\hat{R}_r(T)=\Theta(r^2\beta(T))$ for all $T\in
\mathcal{T}$.
