  We show that for any fixed dense graph G and bounded-degree tree T on the
same number of vertices, a modest random perturbation of G will typically
contain a copy of T . This combines the viewpoints of the well-studied problems
of embedding trees into fixed dense graphs and into random graphs, and extends
a sizeable body of existing research on randomly perturbed graphs.
Specifically, we show that there is $c = c(\alpha,\Delta)$ such that if G is an
n-vertex graph with minimum degree at least $\alpha n$, and T is an n-vertex
tree with maximum degree at most $\Delta$ , then if we add cn uniformly random
edges to G, the resulting graph will contain T asymptotically almost surely (as
$n\to\infty$ ). Our proof uses a lemma concerning the decomposition of a dense
graph into super-regular pairs of comparable sizes, which may be of independent
interest.
