Spanning trees in randomly perturbed graphs

A classical result of Komlós, Sárközy, and Szemerédi states that every n ‐vertex graph with minimum degree at least (1/2 +  o (1)) n contains every n ‐vertex tree with maximum degree O ( n / log n ) . Krivelevich, Kwan, and Sudakov proved that for every n ‐vertex graph G α with minimum degree at least αn for any fixed α  > 0 and every n ‐vertex tree T with bounded maximum degree, one can still find a copy of T in G α with high probability after adding O ( n ) randomly chosen edges to G α . We extend the latter results to trees with (essentially) unbounded maximum degree; for a givenn o ( 1 ) ≤ Δ ≤ c n / log n and α  > 0, we determine up to a constant factor the number of random edges that we need to add to an arbitrary n ‐vertex graph with minimum degree αn in order to guarantee with high probability a copy of any fixed n ‐vertex tree with maximum degree at most Δ.