  Let G be an n-vertex graph that contains linearly many cherries (i.e., paths
on 3 vertices), and let c be a coloring of the edges of the complete graph K_n
such that at each vertex every color appears only constantly many times. In
1979, Shearer conjectured that such a coloring c must contain a properly
colored copy of G. We establish this conjecture in a strong form, showing that
it holds even for graphs G with O(n^(4/3)) cherries and moreover this bound on
the number of cherries is best possible up to a constant factor. We also prove
that one can find a rainbow copy of such G in every edge-coloring of K_n in
which all colors appear bounded number of times.
  Our proofs combine a framework of Lu and Szekely for using the lopsided
Lovasz local lemma in the space of random bijections together with some
additional ideas.
