{'fraction_non_alphanumeric': 0.05022072764008248, 'fraction_numerical': 0.0163988873666293, 'mean_word_length': 3.395231433611094, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 34, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Spanning Trees in Graphs of High Minimum Degree with a Universal Vertex I: An Approximate Asymptotic Result

In this paper and a companion paper, we prove that, if m is sufficiently large, every graph on m+1 vertices that has a universal vertex and minimum degree at least ⌊ 3 ⌋ contains each tree T with m edges as a subgraph. The present paper already contains an approximate asymptotic version of the result. Our result confirms, for large m, an important special case of a recent conjecture by Havet, Reed, Stein, and Wood.


Introduction
A recurring topic in extremal graph theory is the use of degree conditions (such as minimum/average degree bounds) on a graph to prove that it contains certain subgraphs. One of the easiest classes of subgraphs for which this question is not yet properly understood are trees. This is the focus of the present paper.
Clearly, any graph of minimum degree exceeding m − 1 contains a copy of each tree with m edges: Just embed the root of the tree anywhere in the host graph, and greedily continue, always embedding vertices whose parents have already been embedded. The bound on the minimum degree is sharp (see below).
Our paper is one of a large number which discuss possible strengthenings of the above observation by replacing the minimum degree condition with a different condition on the degrees of the host graph. One of these is the Loebl-Komlós-Sós conjecture from 1995 (see [EFLS95]), which replaces the minimum degree with the median degree. This conjecture has attracted a fair amount of attention over the last decades, and has been settled asymptotically [HKP + a, HKP + b, HKP + c, HKP + d]. More famously, Erdős and Sós conjectured in 1963 that every graph of average degree exceeding m − 1 contains each tree with m edges as a subgraph. This conjecture would be best possible, since no (m−1)-regular graph contains the star K 1,m as a subgraph. Alternatively, consider a graph that consists of several disjoint copies of the complete graph K m ; this graph has no connected (m + 1)-vertex subgraph at all. Note that for these examples it does not matter whether we considered the average degree (as in the Erdős-Sós conjecture) or the minimum degree (as in the observation above).
The Erdős-Sós conjecture poses an extremely interesting question. It is trivial for stars, and it holds for paths by an old theorem of Erdős and Gallai [EG59]. It also holds when some additional assumptions on the host graph are made, see for instance [BD96,Hax01,SW97]. In the early 1990's, Ajtai, Komlós, Simonovits and Szemerédi announced a proof of the Erdős-Sós conjecture for sufficiently large m.
It is well-known that every graph of average degree > m has a subgraph of minimum degree > m 2 . So, if it were true that every graph of minimum degree exceeding m 2 contained each tree on m edges, then the Erdős-Sós conjecture would immediately follow. Of course, the statement from the previous sentence is not true: It suffices to consider the examples given above. Still, for bounded degree spanning trees an approximate version of the statement does hold. Komlós, Sarközy and Szemerédi show in [KSS01] that every large enough (m + 1)-vertex graph of minimum degree at least (1 + δ) m 2 contains each tree with m edges whose maximum degree is bounded by cn log n , where the constant c depends on δ. Variations of the bounds and the size of the tree are given in [BPS18,CLNS10]. However, the result is essentially best possible in the sense that (even if the minimum degree of the host graph is raised) it does not hold for trees of significantly larger maximum degree [KSS01].
So, if we wish to find a condition that guarantees we can find all trees of a given size as subgraphs, only bounding the minimum degree is not enough. Nevertheless, there can be at most one vertex of degree at least m 2 in any tree on m + 1 vertices, and so, we might not need many vertices of large degree in the host graph. Therefore, it seems natural to try to pose a condition on both the minimum and the maximum degree of the host graph.
The first conjecture of this type has been put forward recently by Havet, Reed, Stein, and Wood [HRSW16]. They believe that a maximum degree of at least m and a minimum degree of at least ⌊ 2m 3 ⌋ is enough to embed all m-edge trees.
Conjecture 1.1 (Havet, Reed, Stein, and Wood [HRSW16]). Let m ∈ N. If a graph has maximum degree at least m and minimum degree at least ⌊ 2m 3 ⌋ then it contains every tree with m edges as a subgraph.
The conjecture holds if the minimum degree condition is replaced by (1 − γ)m, for a tiny but explicit 1 constant γ, and it also holds if the maximum degree condition is replaced by a large function 2 in m [HRSW16]. An approximate version of the conjecture holds for bounded degree trees and dense host graphs [BPS18].
As further evidence we shall prove, in this paper and its companion paper [RS19b], that Conjecture 1.1 holds for sufficiently large m, under the additional assumption that the graph has m + 1 vertices, i.e., when we are looking for a spanning tree. That is, building on the results from the present paper, we will show the following theorem in [RS19b].
Theorem 1.2. [RS19b] There is an m 0 ∈ N such that for every m ≥ m 0 every graph on m + 1 vertices which has minimum degree at least ⌊ 2m 3 ⌋ and a universal vertex contains every tree T with m edges as a subgraph.
Observe that Theorem 1.2 is easy if T has a vertex t that is adjacent to a set L of at least ⌈ m 3 ⌉ leaves. We root T at v, embed t in the universal vertex v * of G, greedily embed T − L, and then embed L in neighbours of v * . This is possible since v * is universal.
It turns out that this approach can be extended if, for a small positive number δ, the tree T contains a vertex adjacent to at least δn leaves. Although the greedy argument no longer works, we will be able to prove a result, namely Lemma 1.3 below, which achieves the embedding of any tree T as above. This lemma will be crucial for the proof of Theorem 1.2 in our companion paper [RS19b]. Lemma 1.3. For every δ > 0, there is an m δ such that for any m ≥ m δ the following holds for every graph G on m + 1 vertices which has minimum degree at least ⌊ 2m 3 ⌋ and a universal vertex. If T is a tree with m edges, and some vertex of T is adjacent to at least δm leaves, then G contains T .
Also, the results from the present paper alone imply an approximate asymptotic version of this theorem.
Theorem 1.4. For every δ > 0, there is an m δ such that the following holds for every m ≥ m δ and every graph G on m + 1 vertices which has minimum degree at least ⌊ 2m 3 ⌋ and a universal vertex. If T is a tree with at most (1 − δ)m edges, then G contains T .
Both Theorem 1.4 and Lemma 1.3 follow from Lemma 2.1, which is stated in Section 2, and whose proof occupies almost all the remainder of this paper. In the companion paper [RS19b], we will prove the full Theorem 1.2, building on Lemma 1.3 and another auxiliary result, namely Lemma 7.3, which is to be stated and proved in the last section of the present paper (Section 7).
Let us end the introduction with a very short overview of our methods of proof. A more detailed overview can be found in Section 3.
Given a tree T we wish to embed in the host graph G, we first cut T into a constant number of connecting vertices, and a large number of very small subtrees. Applying regularity to G, we can ensure that all those small trees that are not just leaves can be embedded into matching structures we find in the reduced graph of the regularised graph G. This is more complicated than in earlier work on tree embeddings using the regularity approach, as our assumptions are too weak to force one matching structure we can work with throughout the whole embedding. Instead, we have to employ ad-hoc matchings, plus some auxiliary structures, one for each of the connecting vertices. Finally, we have to deal with the leaves adjacent to connecting vertices. These are more difficult to embed than the other small trees, because an embedded vertex might only see two thirds of the graph, and there is no way to reach the remaining third of the graph in only one step. For this reason, we have to come up with a delicate strategy on where we place the connecting vertices, in order to ensure that at the very end of the embedding process we will be in a position to embed all these leaves at once with a Hall-type argument.
2 The Proof of Theorem 1.4 The lemma behind the two results we stated in the introduction (Lemma 1.3 and Theorem 1.4) is the following.
Lemma 2.1. For every δ > 0, there is an m δ such that for any m ≥ m δ and α with δ ≤ α ≤ 1 the following holds. Let G be an (m + 1)-vertex graph of minimum degree at least ⌊ 2m 3 ⌋, with w ∈ V (G). Let T be a tree with at most (1 − α)m edges, with t ∈ V (T ). If no vertex of T is adjacent to more than αm leaves, then one can embed T in G, mapping t to w.
Let us now show how Lemma 2.1 implies the results from the introduction. Here is the proof of the lemma that we will need in the companion paper [RS19b].
Proof of Lemma 1.3. Let m δ be given by Lemma 2.1 for input δ. Given G and T as in Lemma 1.3, we let t be a vertex of T having the maximum number of leaf neighbours. We let L be the set of its leaf neighbours and set α := |L| m . By assumption, δ ≤ α ≤ 1, so we may apply Lemma 2.1 to obtain an embedding of T − L in G with t embedded in the universal vertex of G. We can then arbitrarily embed the vertices of L into the remaining vertices of G. Now comes the proof of the approximate result.
Proof of Theorem 1.4. Let m δ be the maximum of the numbers m δ given by Lemma 2.1 and by Lemma 1.3 for input δ. Given G and T as in the theorem, consider a vertex of T with the maximum number of leaf neighbours, say these are βm leaf neighbours. If β ≤ δ, we are done by Lemma 2.1. If β > δ, we are done by Lemma 1.3.

A Sketch of the Proof of Lemma 2.1
The purpose of this section is to give some more detailed insight into the proof of Lemma 2.1, going a little more below the surface than in the Introduction.
We remark that for the understanding of the rest of the paper, it is not necessary to read this section (but we hope it will be helpful).
The number m δ will be chosen in dependence of the output of the regularity lemma for some constant depending on δ. Given now the approximation constant α, the tree T and the host graph G, we prepare each of T and G separately for the embedding.
Similar as in earlier tree embedding proofs [AKS95, HKP + d, PS12], we cut T into a set W of seeds (connecting vertices), such that W has constant size, and a large set T of very small subtrees. The trees in T are only connected through W , and they each have size < βm, where β is a small constant (smaller than all other constants in this paper).
Differently from earlier approaches to tree embeddings, we now categorise the small trees contained in T : They fall into three categories: trees consisting of a leaf of T , trees that are smaller than a (huge) constant, and trees that are larger than this constant. We name the categories L, F 1 and F 2 . The last category is further subdivided into two sets, F ′ 2 and F 2 \ F ′ 2 , according to whether the small tree is adjacent to one or more of the connecting vertices. Each seed from W may have trees of any (or possibly all) of these categories hanging from it (and there may also be seeds hanging from it). The details of this cut-up of T is explained in Section 5.1.
Next, in Section 5.2, we order and group the seeds obtained from this decomposition. Our strategy of ordering the seeds takes into account their position in a natural embedding order, but also the number of leaves hanging from them. We will come back to this point at a later stage during this outline, and will then explain the why and how of the ordering.
Independently, in Section 6.1.1, we regularize the host graph G, with parameter ε, such that β ≪ ε ≪ α. (For an introduction to regularity, see Section 4.3.) Furthermore, we partition each of its clusters C arbitrarily into subsets CW , C Z , C F 1 , C F 2 , CṼ of appropriate sizes into which we aim to embed the different parts of the tree, namely, W , L, F 1 , and F 2 , while the last subset, CṼ , is reserved for neighbours of seeds in trees of F 2 . The set of these neighbours will be denoted byṼ .
We fix a matching M F 2 in the reduced graph R G . This matching will be used when we embed the trees from F 2 . More precisely, we will embed each treeT ∈ F 2 ∪ F ′ 2 into C F 2 ∪ D F 2 for a suitable (i.e. sufficiently unoccupied) edge CD ∈ M F 2 , except for the root rT ofT . The root rT will go to one of the subsets C ′Ṽ , for a suitable cluster C ′ that connects CD with the cluster containing the seed adjacent toT . In caseT ∈ F ′ 2 , which means thatT contains a second vertexṽ fromṼ , we embedṽ into one of the subsets C ′′ V , for a suitable cluster C ′′ . Throughout the embedding process, we will keep each of the edges of M F 2 as balanced a possible. That is, the sets of used vertices in the corresponding slices C F 2 or D F 2 on either side of such an edge never differ by more than βm.
Observe that since we do not have enough space in the slices CṼ for all roots of trees in F 1 (because we have no control over the number of trees in F 1 ), we need to proceed differently with the small trees from F 1 . For embedding these trees, we use a family of matchings M, one for each embedded seed s. Since these matchings M are possibly different for each s, we now will have to keep the set of all slices C F 1 balanced. This is not easy but possible since the trees from F 1 have constant size, and we choose M so that it intersects the neighbourhood of s in a nice way.
There are some problems with balancing the edges of M, since clearly, s might fail to see each side of each edge from M, which makes it difficult to balance those edges of M that are not completely contained in the neighbourhood of s in R G . To overcome this problem, we employ two auxiliary matchings which we we combine with M to obtain a partition of almost all of V (R G ) with short paths. We call these structures good path partitions and, together with the matchings M, they will be defined and proved to exist in Subsection 4.2.
The actual embedding of the tree will be performed as follows. In Sections 6.2 and 6.3, we go through the seeds in a connected way, and embed each seed s together with all the trees from F 1 ∪ F 2 at s in the corresponding slices in the way we discussed above. We leave out any leaves from L, as we will deal with them in the final phase of the embedding.
Whenever we have embedded one seed s and its trees, we proceed to the next seed and its trees. Because of the way we embed in the slices, and the way we chose our matchings, all of this will go through just fine, and we will always have enough space to embed. However, if we do not take care where exactly we embed the seeds, we may run into problems in the final phase when we want to embed the leaves. For instance, it might happen that all seeds that are adjacent to vertices in L have been embedded into vertices having the same neighbourhood in R G . As this neighbourhood might be only two thirds of the vertices of R G , the leaves might not fit.
For this reason, we take some extra care when choosing the target clusters and the actual images for the seeds (this happens in Section 5.2). As already shortly mentioned above, we order the seeds into a system of groups according to the number of leaves hanging from them. Then we reorder this order a bit, according to the order the seeds appear in our planned embedding order. Also, each seed s will be assigned a relevant set X s of seeds that come before it. In the actual embedding, in Subsection 6.2, we choose the image ϕ(s) of a given seed s in a way that ϕ(s) has many neighbours outside the union of the neighbourhoods of ϕ(X s ). (We remark that is is crucial here that no vertex of T is adjacent to more than αm leaves.) This precaution will ensure that for each subset of seeds, their images have enough neighbours in Z := C Z . Therefore, we will be able to embed all the leaves in L at once by using Hall's theorem. The whole procedure will be explained in detail in Subsection 6.4.
The last section of this paper, Section 7, is devoted to the statement and proof of an auxiliary result, Lemma 7.3, that deals with a similar situation as the one treated by Lemma 2.1. We will need Lemma 7.3 in our companion paper [RS19b] (in addition to Lemma 2.1). The main difference to the situation here is that there, a small part of the tree is already embedded (and thus possibly blocking valuable neighbourhoods), but, on the positive side, throughout [RS19b], we will be able to assume that no seed is adjacent to many leaves, and so we can assume this as well in Lemma 7.3.

An edge-double-counting lemma
We will need the following easy lemma.
Lemma 4.1. Let G be a graph on n vertices, let 0 < ψ < 1 3 , and let S ⊆ V (G) be such that each vertex in S has degree at least ( 2 3 − ψ)n. Then there are at least ( 1 3 + √ ψ 10 )n vertices in G that each see at least ( 1 2 − √ ψ)|S| vertices of S.
Proof. We let A ⊆ V (G) denote the set of all vertices that see at least ( 1 2 − √ ψ)|S| vertices of S. Writing e(S, V (G)) for the number of all edges touching S, where edges inside S are counted twice, we calculate that and conclude that as desired.

Matchings and good path partitions
The purpose of this subsection is to find some matchings in a graph H (which will later be the reduced graph R G of our host graph G, see Section 4.3 for a definition of the reduced graph). Actually we will combine some of the matchings we find to specific covers of H with short paths. These structures will be used for the embedding of T in the proof of Lemma 2.1, more specifically in Subsection 6.3. The important result of this section is Lemma 4.3, which provides us with the desired structures. We need a quick definition before we start. For any graph H, and any N ⊆ V (H), an N-good matching is one whose edges each have at most one vertex outside N.
We will start by proving the following lemma.
Lemma 4.2. Let 0 < ξ < 1 20 and let H be a p-vertex graph of minimum degree at least ( 2 3 − ξ)p. Let N ⊆ V (H) be such that |N| = ⌈( 2 3 − 2ξ)p⌉. Then H − N contains a set Y of size at most ⌊5ξp⌋ + 1 such that H − Y has an N-good perfect matching.
Proof. First, note that we can greedily match all but a set X of at most ⌊5ξp⌋ vertices from V (H) \ N to N, simply because of the condition on the minimum degree. Now, take any maximal N-good matching M in the graph H that covers all vertices of V (H) \ (N ∪ X). We would like to see that M covers all but at most vertex of H − X, so for contradiction assume that N \ V (M) contains at least two vertices. By the maximality of M, no vertex D ∈ N \ V (M) is adjacent to any of the other uncovered vertices in N, and no two vertices D, D ′ ∈ N \ V (M) can be adjacent to different endpoints of an edge in M. So, for each edge EF ∈ M, we know that either one of the endvertices, say E, sees no vertex in N \ V (M), or E and F each see only one vertex in N \ V (M) (and that is the same vertex). This means that at least one of the vertices in N \ V (M) sees at most half of the vertices in V (M), and thus less than half of the vertices in H − X, a contradiction to our condition on the minimum degree.
Before we state the second lemma of this section, we need another definition.
An N-out-good path partition of a graph H, with N ⊆ V (H), is a set P of disjoint paths, together covering all the vertices of H, such that for each P ∈ P one of the following holds: • P = AB, with A, B ∈ N; • P = ABCD, with B, C ∈ N; or • P = ABCDEF , with B, C, D, E ∈ N.
(Note that if P has four vertices, then there is no restriction on the whereabouts of A and D, and similar for six-vertex paths P .) An N-in-good path partition of a graph H, with N ⊆ V (H), is a set P of disjoint paths, together covering all the vertices of H, such that for each P ∈ P one of the following holds: • P = AB, with A, B ∈ N; • P = ABCD, with A, D ∈ N; or Now we are ready to state the main result of this section. Note that the first item is a direct consequence of the previous lemma, and all structures exist independently of each other.
Lemma 4.3. Let 0 < ξ < 1 20 , and let H be a p-vertex graph of minimum degree at least ( 2 3 − ξ)p. Let N ⊆ V (H) be any set with |N| = ⌈( 2 3 − 2ξ)p⌉. Then H contains a set X of at most ⌊15ξp⌋ + 1 vertices, such that • H − X has an (N \ X)-good perfect matching; • H − X has an (N \ X)-in-good path partition; and • H − X has an (N \ X)-out-good path partition.
Proof. Lemma 4.2 provides us with a set Y and an N-good perfect match- We take a maximal matchingM A inside H[A]. CallÃ the set of vertices in A not covered byM A . We augmentM A to a matching M A by matching as many vertices ofÃ as possible to a set A ′ of vertices in N. Because of the minimum degree condition of the lemma, and sinceÃ is an independent set, we can ensure that for the set Z ⊆Ã of vertices not covered by M A we have |Z| ≤ 5ξp. Moreover, we can choose A ′ such that for each D ∈ A ′ , the other endvertex of the edge of M containing D also lies in N. Let Z ′ denote the set Z is matched to in M. Now we define a second auxiliary matching M B in a very similar way. Matching M B consists of edges with both ends in B \ Z ′ , and a matching of almost all the remaining vertices of B \Z ′ to a set B ′ of vertices from N, such that for each D ∈ B ′ , the other endvertex of the edge of M containing D also lies in N. We can ensure that at most ⌊5ξp⌋ vertices of B \ Z ′ are not covered by M B . Let X ′ denote the union of the set of these vertices and their partners in M, and set X : Then, discarding any edge that touches X from M, M A and M B , we find that the union of M and M A gives an (N \ X)-in-good path partition of H − X. Also, the union of M and M B gives the desired N-out-good path partition. (Note that the four-vertex paths from these partitions have either one or two vertices outside N \ X.) Finally, M is an (N \ X)-good matching of H − X.

Regularity
We need to quickly discuss Szemerédi's regularity lemma and a couple of other preliminaries regarding regularity. Readers familiar with this topic are invited to skip this subsection.
The density of a pair (A, It it well known that regular pairs behave, in many ways, like random bipartite graphs with the same edge density. The following well known and easy-to-prove facts (see for instance [KSS02]) state that in a regular pair almost every vertex is typical to any given significant set, and also that regularity is inherited by subpairs. More precisely, if (A, B) is an ε-regular pair with density d, then • for any ε-significant B ′ ⊂ B, all but at most ε|A| vertices from A are ε-typical to B ′ ; and • for each δ ≥ 0, and for any subsets Szemerédi's regularity lemma states that every large enough graph has a partition of its vertex set into a bounded number of parts, of almost equal sizes, such that almost all pairs of partition sets are ε-regular.
Lemma 4.4 (Szemerédi's regularity lemma). For every ε > 0 and M 0 ∈ N there are M 1 , n 0 ∈ N such that for all n ≥ n 0 the following holds.
As usual, we define the reduced graph R G corresponding to this decomposition of G as follows. The vertices of R G are all clusters V i (i = 1, . . . , p), and R G has a edge between V i and V j if the pair (V i , V j ) is ε-regular, and has density at least 10 √ ε. By standard calculations (see for instance [KSS02]), and assuming we take where δ w (R G ) is the weighted minimum degree. (That is, the densities of the pairs of clusters provide weights on the edges of R G , and the weighted degree of a vertex is the sum of the corresponding edge-weights. The weighted minimum degree is the minimum of these degrees. Observe that δ w (R G ) ≤ δ(R G ) since weights do not exceed 1.) Almost all vertices of any cluster C ∈ V (R G ) are typical to almost all significant sets, in the following sense. If Y is a set of significant subsets of clusters in V (R G ), then all but at most √ εs vertices v ∈ C are typical with respect to all but at most √ ε|Y| clusters in Y. ( To see this well-known observation, assume that the set C ′ ⊆ C of vertices not satisfying (2) is larger than √ εs. Then Thus there is a Y ∈ Y such that more than ε|C| vertices in C are not typical to Y , a contradiction. Regularity will help us when embedding small trees into a pair of adjacent clusters of R G .
Lemma 4.5. Let CD be an edge of R G , and let U ⊆ G with |C \U|, |D \U| ≥ √ ε|C|. LetT be a tree of size ≤ ε|C| with root rT . ThenT can be embedded into G, withT − rT going to (C ∪ D) \ U, and with rT going to any prescribed set of ≥ 2ε|C| vertices of C, or to any prescribed set of ≥ 2ε|C| vertices of C ′ , where C ′ is any other cluster of R G that is adjacent to D.
Proof. We construct the embeddingT levelwise, starting with the root, which is embedded into a typical vertex of (C ∪ D) \ U. At each step i we ensure that all vertices of level i are embedded into vertices of C \ U (or D \ U) that are typical with respect to the unoccupied vertices of D \ U (or C \ U). This is possible, because at each step i, and for each vertex v of level i, the degree of a typical vertex into the unoccupied vertices on the other side is at least 4ε|C|, and there are at most ε|C| nontypical vertices and at most |T | ≤ β|C| already occupied vertices.

Preparing the tree 5.1 Cutting a tree
In this section, we will show how any tree T can be cut up into small subtrees and few connecting vertices. The ideas is that later, we can use regular pairs to embed many tiny trees.
We will make use of a procedure which in a very similar shape has already appeared in [AKS95, HKP + d, PS12], although there, no distinctions between the trees from L, F 1 , F 2 , were made. The resulting cut-up is given in the following statement.
Lemma 5.1. For any m ∈ N, for any tree T on m + 1 vertices, and for any (c) |V (T )| = 1 for every treeT ∈ L; has exactly one neighbour in W ; (g) eachT ∈ F ′ 2 has exactly two neighbours in W ; and The vertices in W will also be called the seeds of T .
Proof. In a sequence of at most 1 β steps i, we define vertices w i and trees T i as follows. Set T 0 := T . Now, for each i > 0, let w i ∈ V (T i−1 ) be a vertex at maximal distance from r (the root of T ) such that the components of T i − w i that do not contain r each have size at most βm. Delete w i and all of these components from T i+1 to obtain T i . We stop when we reach r, which will be the last vertex w i to be defined.
Let W 0 be the union of all w i , and let T 0 be the family of the trees in T − W 0 . These two sets already fulfill items (a) and (b). (To see (b), note that at each step i, we cut off βm vertices. Hence we actually have that |W 0 | ≤ 1 β .) In order to obtain sets W , T that also fulfill items (f ) and (g), we add some vertices to W 0 as follows. For eachT ∈ T 0 that has ℓ > 2 neighbours v 1 , v 2 , . . . , v ℓ in W 0 , we add to W 0 a set of at most ℓ−1 vertices w ′ j from V (T ) that separate all v i 's from each other. Note that these are at most 1 β vertices in total (counting over all affectedT ), since each of the newly added vertices w ′ j can be associated to one of the 'old' vertices v j from W 0 such that w ′ j lies between v j and r.
So, letting T 1 be the family of the trees in T − W 1 , the new sets W 1 , T 1 still fulfill (a) and (b) (actually, we have that |W 1 | ≤ 2 β ). They furthermore have the property that each of the trees in T 1 has at most two neighbours in W 1 .
We modify our sets once more to ensure that only the large trees can have two seed neighbours. We proceed as follows. For eachT ∈ T 1 that has at most 1 β vertices and is adjacent to two seeds w 1 , w 2 ∈ W 1 , we add to W 1 all vertices on the path that connects the two seeds w 1 , w 2 . In total, these are at most 1 β · |W 1 | ≤ 2 β 2 vertices. Call the new set of seeds W . Defining T as the family of the trees in T − W , and adequately dividing the family T into three families L, F 1 , F 2 , and letting F ′ 2 be the appropriate subset of F 2 , we thus obtained sets that fulfill all properties of the claim. (Note that (h) follows directly from (e), (g) and the observation that |Ṽ | ≤ 2|F ′ 2 | < 2|T −r|

Ordering the seeds of a tree
In order to be able to choose well the clusters of V (R G ) into which we will embed the seeds other than r later on, let us now define a convenient ordering of the seeds of a tree T with a cut-up as in Section 5.1. Together with this ordering we will define a set of relevant seeds X s for each seed s of the tree, and ensure that the seeds in X s come before s in the ordering. The importance of this ordering and the sets X s is that later, when we embed the parts of the cut-up tree in G, it will turn out that the small trees that are most difficult to embed are those from L, this is, the leaves of T that hang off seeds. An embedded seed has only degree 2 3 m in G, of which a large part might already be used, so if we do not take sufficient care, we will get stuck when embedding the leaves. For this reason we have to choose very well into which clusters the seeds go, and the sets X s will help us with this.
The reader might wish to skip the remainder of this unfortunately rather technical section at a first reading, because everything we do here is only necessary for the embedding of L. Even the embedding of L can be followed with only a vague understanding of the definitions of the present section if the reader takes the 'Degrees of the embedded seeds into Z' as stated in Subsection 6.2.4 for granted.

Grouping and ordering
Let us start with the ordering. Assume we are given a tree T which has been treated by Lemma 5.1 for some β > 0, let W denote the set of seeds we obtained. Throughout the rest of this section we will assume that (This can be assumed by adding some artificial seeds to the tree T . We will explicitly discuss why this can be done in Subsection 6.1.2.) We will order the seeds in two different ways, before we get to the third and final order. The first order is determined by the number of leaves hanging from each seed, the second order is determined by the position of the seeds in the tree T , and the third order is a mixture of both. We explain the orderings in detail in the following.
We start by ordering the seeds in a way that the number of leaf children of the seeds is non-increasing, and we call this the size order σ on the seeds.
For each j = 0, . . . , j * , we partition the set of all seeds into 2 j * −j consecutive groups of size 2 j · 47, under the size order σ. We call these the large groups. Clearly, each large group of size exceeding 47 is the union of two large groups half its size.
We break up each group B of size 47 into twelve consecutive groups (consecutive under σ) of the following sizes: 4, 4, 4, 4, 5, 4, 4, 4, 4, 5, 4, 1. (4) We call these the small groups. (So the small subgroup of size 1 of B consists of the very last seed of B in the size order σ.) We say the second and sixth group of size four are of type 1 (they are marked in boldface in (4)). The remaining groups of size four (i.e. the first, third, fourth, fifth, seventh, eighth and ninth group of size four) will be called type 2. It would be difficult to embed the seeds in the size order σ, as this enumaration might not be suitable for embedding the tree in a connected way. For this reason, we employ a second order τ , which we call the transversal order, obtained by performing a preorder tranversal on T , starting with the root r, and then restricting this order to W . (The transversal order is the actual order the seeds will be embedded in.) The third order, which we call the rearranged order ρ, is obtained by reordering the order σ. First, we reorder the seeds in each small group so that each small group is ordered according to τ . Next, for every large group B of size 47, we reorder all its subgroups so that their first seeds form an increasing sequence in the transversal order τ . Finally, for every large group B of size > 47 (in successive steps according to the group size), we reorder the two subgroups within B so that the first subgroup contains the first seed in B under the transversal order τ (i.e. we reorder them such that the first seed of B under τ becomes the first seed of B). This finishes the definition of the rearranged order ρ.
We note that ρ maintains the structure given by breaking down the set of seeds into large and small groups. That is, if we partition the set of all seeds into 2 j * −j consecutive groups under ρ of sizes 2 j · 47, we obtain the same groups as above for σ. Further, each group of size 47 breaks down into twelve small groups as above, although these are no longer ordered as in the sequence from (4). We note that each of the small and large groups under ρ remains a consecutive set of elements if viewed under the size order σ.
We will embed according to τ but momentarily work with ρ. We write s < ρ s ′ to denote that s comes before s ′ in order ρ (and similar for τ ).

Sequences
In this subsection, we will follow the rearranged order ρ. We define for each large group B two sequences where j is such that |B| = 2 j · 47, and vertices x B i , y B i ∈ B are as specified in what follows.
We construct our sequences inductively. For j = 0, we have to deal with all groups of size 47. For each such group B, we take x B 1 = y B 1 as the first seed of the group. The first seed of the second, third, fourth, fifth and sixth small subgroup of B is chosen as respectively. The first seed of the seventh, eigth, ninth, tenth, eleventh and twelfth small subgroup of B is chosen as y B 2 , y B 3 , y B 4 , y B 5 , y B 6 , y B 7 , respectively. (We always work under ρ, both when talking about the 'first seed of a group' and when talking about the 'ith subgroup'.) For j ≥ 1, we have to deal with all large groups of size 2 j · 47. For each such group B, do the following. By construction B is made up of two large subgroups of size 47 · 2 j−1 , say these are B ′ and B ′′ (in this order, under ρ).
We let x B i := y B ′ i for all 1 ≤ i ≤ j + 6, and we set This finishes the definition of the sequences. We remark that we will only use the sequences (x i ) in what follows (the sequences (y i ) were only used to make the definition of (x i ) more convenient).
Observe that for all blocks B, and for all i < j, we have that x B i < τ x B j .

Relevant seeds
In order to be later able to choose well the clusters we embed the seeds into (which in turn will enable us to embed the leaves at an even later stage), we need to define, for each seed s, a set X s of relevant seeds for s, as follows.
Definition 5.2 (Relevant seeds for s). Let s be a seed of T , and let B be the small group s belongs to.
(a) If B is a group of four of type 2, and s is the last seed of B, then we set (b) If s is not the first seed of B, and, in case B is a group of four of type 2, s is not its last seed, then we set (c) If s is the first seed of B, then we set Observe that if s only appears as a first vertex in any of the sequences (xB i ), then X s = ∅.
Let us make a quick observation which follows directly from the definition of the order ρ, of the sequences (x i ) and of the sets X s .
Observation 5.3. Let s be a seed. Then for all x ∈ X s it holds that x < τ s.
Finally, we choose for the output of Lemma 2.1. So, given the approximation constant α, satisfying 1 ≥ α ≥ δ, we will have that with the explicit dependencies given above. Now, given m ≥ m δ , and given an (m + 1)-vertex graph G of minimum degree at least ⌊ 2m 3 ⌋ , and a tree T with at most m − αm edges, rooted at r, we will prepare both T and G for the embedding.

Preparing T for the embedding
We apply Lemma 5.1 to obtain a partition of T into a set W of seeds and a set T of small trees. The small trees divide into F 1 and F 2 , with two-seeded trees F ′ 2 ⊆ F 2 , and the lemma also gives us a setṼ . Set Next, add a set W ′ of vertices to T , each adjacent to r, such that, setting W := W ∪ W ′ , we have |W | = 47 · 2 j * for j * := ⌈log 2 β 2 ⌉.
The only reason for this is that we plan to apply the grouping and ordering of seeds from Subsection 5.2, that is, we would like to see (3) fulfilled. We are going to embed T ∪ W ′ instead of T . Since the number of vertices in W ′ is a constant, space is not a problem. Indeed, clearly, 6.1.3 Preparing G for the embedding As a preparation of G for the embedding, we take an ε 2 -regular partition of G as given by Lemma 4.4 (the regularity lemma), into p clusters, for some p with M 0 < p < M 1 . Consider the reduced graph R G of G with respect to this partition, as defined below Lemma 4.4.
Observe that because of the minimum degree of G and by (1), we have that Let us now partition the clusters of R G further. We will divide each clusters into several slices, into which we plan to embed the distinct parts of the tree T which we identified above.
First of all, we choose a set Z of vertices into which we plan to embed L. More precisely, we arbitrarily choose a set Z ⊆ V (G) of size choosing the same number of vertices in each part of the partition (plus/minus one vertex). Now, we will split up the remainder C \ Z of each cluster C ∈ V (R G ) arbitrarily into four sets CṼ , CW , C F 1 , C F 2 , and a leftover set C \ (Z ∪ CṼ ∪ CW ∪ C F 1 ∪ C F 2 ) which will not be used. The sets are chosen having the following sizes: and This is possible because of (7) and (9). As we mentioned above, the idea behind this slicing up is that we are planning to put each part X of the tree (X ∈ {W ,Ṽ , F 1 , F 2 , L}) into the parts C X of the clusters of R G , or into Z, respectively. We reserve a bit more than is actually needed for the embedding, in order to always be able to choose well-behaved (typical) vertices, and also in order to account for slightly unbalanced use of the regular pairs when embedding the trees from T . Since the sets C X are large enough, regularity properties will be preserved between these sets (cf. Section 4.3).
Let us remark that it is not really necessary to slice the clusters C up as much as we do: the vertices destined to go into slices CṼ and CW are actually so few that they could go to any other slice without a problem. But we think the exposition might be clearer if everything is well-controlled.
Finally, we fix a perfect matching M F 2 of R G which exists because of (10). This matching will be used for embedding the larger trees from T , namely those in F 2 .

The plan
For convenience, for each seed s ∈W , let T s denote the set of all trees from T \ L that are adjacent to s. We are going to traverse the seeds in the transversal order τ , placing each seed s into a suitable cluster S(s) (we will determine this cluster right before embedding s into it). We then embed T s before embedding any other seed. After having embedded all seeds s ∈W and all corresponding trees from T s , we embed all of L in one step at the very end of the embedding process. So, if the seeds are ordered as s 1 , s 2 , s 3 , . . . , s |W | in τ , then we embed in the order and at every point in time, the embedded parts of the tree will form a connected set in T . Each of the three different embedding procedures will be described in detail in one of the following subsections, namely, in Subsection 6.2 (embedding a seed s), in Subsection 6.3 (embedding T s ) and in Subsection 6.4 (embedding L).

Embedding the seeds 6.2.1 Preliminaries
Assume we are about to embed some seed s. Denote by U the set of vertices that, up to this point, have been used for embedding seeds and small trees. So U ∩ Z = ∅ (we will ensure that this will always remain so), and every cluster C ∈ V (R G ) divides into six sets: C ∩ U, C ∩ Z, CW \ U, CṼ \ U, C F 1 \ U, and C F 2 \ U.
Apart from U, it will be useful to have a set U ′ ⊆ C∈V (R G ) (C F 1 \ U) of vertices for which at some point we decided that they will never be used for the embedding. The main use of this set U ′ is that after embedding certain trees from T s ∩ F 1 for some seed s, we can just make all sets C F 1 of clusters C equally 'occupied' by discarding some of the vertices of the emptier sets C F 1 by putting them into U ′ . This will be the only time we add vertices to U ′ . We will make sure that for each seed s the number u ′ s of vertices we add to U ′ while, or directly after, embedding T s is bounded by Since there at most 2 β (original) seeds in the tree, this means that the set U ′ will always stay so small that we can ignore it while embedding.
Throughout the embedding, we will ensure that for each parent u of a seed (the parent u might be a seed, or a vertex fromṼ ) the following holds. If u was embedded in vertex ϕ(u), then we have that ϕ(u) is typical to slice CW for all but at most εp clusters C of R G . (16) Note that by Observation 5.3, by the time we reach a seed s, the 'relevant' seeds in X s have already been embedded into a set ϕ(X s ). Let N Z (X s ) denote the set of all neighbours of vertices from X s in Z. Let N s be the set of corresponding subclusters of the clusters of R G (i.e., N s = N Z (X s )).

Finding the target cluster S(s) for s
Before actually choosing the vertex ϕ(s) we will embed s into, we will determine the target cluster S(s) for a seed s.
Observe that by Lemma 4.1, with ψ := 13ε, we know that at least ( 1 3 + ε 1 3 )m of the vertices of G see a ( 1 2 − ε 1 3 )-portion of the vertices in Z \ N Z (X s ). So, for significantly more than a third of the clusters of R G we have that a significant portion of their vertices see at least ( 1 2 − ε 1 3 ) · |Z \ N Z (X s )| vertices in Z \ N Z (X s ). Because of regularity, and because of (2), this means that for any such cluster C, all but at most an ε-fraction of the vertices in CW has at least ( 1 2 − 3ε 1 3 ) · |Z \ N Z (X s )| neighbours in Z \ N Z (X s ). Choose S(s) as any one of the clusters as above. That is, we choose S(s) such that (α) all but at most ε|S(s)W | vertices of the set S(s)W have degree at least ( and such that in addition (unless s = r, in which case the following two conditions are void), (β) S(s) is adjacent to S(p(s)); (γ) ϕ(p(s)) is typical with respect to S(s)W , where S(p(s)) denotes the cluster the parent p(s) of s was embedded into. Such a choice of S(s) is possible since by (10), cluster S(p(s)) has degree almost 2p 3 in R G , and because of (16).

Embedding seed s into target cluster S(s)
We place s in a vertex ϕ(s) from S(s)W \U such that (A) ϕ(s) is a neighbour of ϕ(p(s)) (where p(s) is the parent of s, and if s = r this restriction is empty); (B) ϕ(s) is typical to CW for all but at most εp clusters C ∈ V (R G ) \ S(s); (C) ϕ(s) is typical to CṼ for all but at most εp clusters C ∈ V (R G ) \ S(s); (E) ϕ(s) is typical to C Z for all but at most εp clusters C ∈ V (R G ) \ S(s).
Such a choice is possible since by (2), almost all vertices in any given cluster are typical with respect to any fixed significant subsets of almost all other clusters.
In particular, (E) implies that

Degrees of the embedded seeds into Z
The reason for our choice of S(s) as a cluster fulfilling property (α) from Subsection 6.2.2 is that it allows us to accumulate degree into Z. More precisely, if we consider a seed s together with its relevant seeds X s , then we know that the union of their neighbourhoods in Z is significantly larger than the neighbourhood of s alone. Better still, the more vertices X s contains, the larger becomes our bound on this neighbourhood. We make this informal observation more precise in the following claim. (iv) If B is large, say of size 47 · 2 j , then ..,j+6 is the sequence defined in Subsection 5.2.2. Proof. This follows rather directly from (α) and (E) (from Subsections 6.2.2 and 6.2.3, respectively), from (17), and from the definition of the set X s of relevant seeds (Definition 5.2). For instance, we can calculate the bound in item (i) by using (17), (α), (E), and Definition 5.2 (b) to see that For item (iv), we need to take slightly more care with the calculation. Note that the degree in to Z of the image of the first seed is off 2 3 |Z| by at most 3ε 1 3 |Z|. The degree of second seed's image is only off 1 2 |Z| by less than 3ε |Z| 4 , and so on, which means we can actually bound the error in our estimate for the size of the joint neighbourhod in item (iv) by 2 · 3ε 1 3 |Z| ≤ ε 1 4 · |Z|.

Embedding the small trees
Assume we have sucessfully embedded a seed s, and are now, before we proceed to the next seed, about to embed all small trees from T s (while still leaving any leaves from L adjacent to s unembedded).
Our plan is to embed those trees of T s that belong to F 1 into C∈V (R G ) C F 1 , and those trees of T s that belong to F 2 into C∈V (R G ) C F 2 . We first explain how we deal with the larger trees, i.e. those in F 2 \ F ′ 2 , and those in F ′ 2 . After that we explain how we deal with the constant sized trees, i.e. those in F 1 . Note that actually, it does not matter in which order we deal with the sets

Embedding the trees from
For eachT ∈ T s ∩ (F 2 \ F ′ 2 ), let rT denote its root. We plan to put rT into C ′Ṽ \ U for some suitable cluster C ′ . (We will explain below how exactly we do that.) For the rest of V (T ), we proceed as follows.
Recall that we defined a perfect matching of R G near the end of Section 6.1.1. Choose an edge CD of M F 2 that contains at least 3ε · m p unused vertices in each of C F 2 , D F 2 . If |C F 2 \ U| ≥ |D F 2 \ U|, we will aim at putting the larger colour class ofT −rT into C F 2 \U, and otherwise, we aim at putting it into D F 2 \ U. Observe that if we manage to do this for every treeT we embed, we can ensure that throughout the process (even when embeeding trees from T s ′ , for some s ′ = s), the edges from M F 2 keep their free space in a more or less balanced way, that is, for all edges C ′ D ′ in M F 2 , Let us now explain how we manage to embedT in this way. Assume our aim is to embed the children of rT in to C F 2 \ U, the grandchildren into D F 2 \ U, the grand-grandchildren into C F 2 \ U, and so on. The embedding ofT − rT will be easy using Lemma 4.5 once we found a vertex ϕ(rT ) to embed rT into, that is, a vertex that is both a neighbour of ϕ(s) and typical with respect to C F 2 \ U.
So we only need to find a suitable vertex for ϕ(rT ), the root ofT (which belongs toṼ ). In order to do so, we first determine a cluster C ′ that is adjacent to both C and S(s), and that fulfills d(S(s), C ′ ) ≥ 1 4 . At least a third of the clusters in R G qualify for this, because of (10). Now, by (C) in the choice of ϕ(s) (in Subsection 6.2.3), we know that ϕ(s) has typical degree into the set C ′Ṽ for all but very few clusters C ′ . Typical degree means that ϕ(s) has at least ( 1 4 − ε 2 ) · |C ′Ṽ | neighbours in C ′Ṽ , and by Lemma 5.1 (h), at most 2βm vertices have been used for earlier vertices fromṼ . So, by (7), we can choose a suitable C ′ such that ϕ(s) has a large enough neighbourhood in C ′Ṽ to ensure it contains a vertex ϕ(rT ) that is typical with respect to Finally, observe that (18) ensures that the space we had assigned to F 2 is enough for embedding all of F 2 \ F ′ 2 .

Embedding the trees from F ′ 2
For eachT ∈ T s ∩ F ′ 2 , we proceed exactly as in the preceding paragraph, except that now, we have to make a small adjustment when we are close to embeddingṽ, the second vertex fromṼ contained in V (T ).
Suppose s ′ is the seed which is adjacent toṽ in T . Because we embed the seeds following the transversal order, we know that s ′ is not yet embedded by the time we deal withT . We take care to embedṽ into a vertex that is typical with respect to almost all the sets CW . That is, the image ofṽ will be chosen such that (16) holds.

Embedding the trees from F 1
We now explain how we embed the trees from T s ∩ F 1 . Note that because of (13) and (15), we have enough space to embed all of T s ∩ F 1 . Furthermore, because the trees from F 1 are small, and because of regularity, we have no problem with the actual embedding of them into the regular pairs of G. The only thing we need to make sure is that the roots of the trees from T s ∩F 1 are embedded into neighbours of ϕ(s), and that we maintain the unused parts of the cluster slices C F 1 balanced at all times.
Since there is no matching like M F 2 that can be used throughout the whole embedding (i.e., for all seeds), we will have to simultaneously keep all of the clusters reasonably balanced. This will be possible because of the rather delicate embedding strategy we employ, and which we will start to explain now.
Preparing the slices C F 1 . Assume we are about to start the embedding process of the trees from T s ∩ F 1 . First of all, note that we can partition the free space C F 1 \ (U ∪ U ′ ) of the slices C F 1 of each of the clusters C ∈ V (R G ) \ {S(s)} into sets Q C 0 , . . . , Q C r for some r, such that |Q C 0 | < 2⌈ε m p ⌉ and |Q C i | = ⌈ε m p ⌉ for i = 1, . . . , r, and such that for each i = 1, . . . , r, either all or none of the vertices in Q C i are adjacent to ϕ(s). The reason for doing this is that we now have total control over where exactly the neighbours of ϕ(s) are (since the sets Q C 0 are small enough to be ignored during this step of the embedding). Observe that the sets Q C i , for i = 1, . . . , r, are large enough to preserve regularity properties, although now we have to replace the regularity parameter ε 2 with ε 2 ε = ε. Consider the graph H with vertex set {Q C i } i=1,...,r,C∈V (R G ) and an edge for each ε-regular pair of sufficient density. Say H has p ′ vertices. By (10), the weighted minimum degree of R G is bounded by δ w (R G ) ≥ ( 2 3 − 13ε)p, and therefore, the weighted minimum degree of H is bounded by δ w (H) ≥ ( 2 3 − 17ε)p ′ . So, by our choice of ϕ(s), in particular by (D) of Subsection 6.2.3, we know that ϕ(s) has neighbours in at least ( 2 3 − 20ε)p ′ of the sets Q C i . Let N consist of a set of ⌈( 2 3 − 20ε)p ′ ⌉ sets Q C i that contain neighbours of s. We apply Lemma 4.3 with ξ := 17ε to H to obtain a set X, of size at most ⌊255εp ′ ⌋ + 1, and an (N \ X)-good matching M, an (N \ X)-in-good path partition P A and an (N \ X)-out-good path partition P B of H − X.
Set Q := C∈V (R G ) {Q C 1 , Q C 2 , . . . , Q C r } \ X. By (13), and by (15), we know that Q is large enough to host all of T s ∩F 1 . In fact, if T s ∩F 1 could be embedded absolutely balanced into the sets Q ∈ Q, then there would even be a leftover space of more than 100ε m p in each of the sets Q. Recall that during the embedding of the trees from T s ∩ F 1 , we will add some vertices to a set U ′ , for keeping better track of the balancing of the edges. We will keep U ′ small, that is, we will ensure that (15) holds.
Preparing T s ∩ F 1 . We now partition the set of trees from T s ∩ F 1 into three sets 3 : the set T Bal contains all the balanced trees, i.e. those trees whose color classes have the same size; the set T N earBal contains all trees having the property that their colour classes differ by exactly one, with the bigger class containing the root; and the set T U nbal contains all the remaining trees, that is all unbalanced trees not belonging to T N earBal .
Phase 1. In the first phase of our embedding, we embed all trees from T Bal , using the matching M. We try to spread these trees as evenly as possible among the edges of M. It is not difficult to see that by Lemma 5.1 (d), it is possible to make the used part of the clusters differ by at most 1 β (but even the more obvious weaker bound 1 β 2 is sufficient for our purposes). At the end of this phase of the embedding, we add to U ′ at most 1 β unused vertices from each of the clusters C ∈ V (M), and can thus make sure each of the clusters has exactly the same number of vertices in C F 1 \ (U ∪ U ′ ).
Phase 2. In the second phase of our embedding, we embed all trees from T U nbal . We group the trees from T U nbal by their number of vertices, which is some number between 3 and 1 β . Then we subdivide these groups according to the number of vertices belonging to the same colour class as their root. The final groups represent the types of trees. Since all trees we consider have order at most 1 β , there are at most 1 β 2 different types. For each of the typesT , say with t vertices, and colour classes of sizes t 1 and t 2 , where the class of size t 1 contains the root, we proceed as follows. We go through the elements of our N-out-good path partition P B in some fixed order, always embedding only a constant number of trees of typeT . In each round, we keep the clusters of H − X perfectly balanced. Only when we run out of trees of typeT , we will (necessarily) have to make a last round, possibly not reaching all elements of P B , and thus unbalancing some of the clusters a bit (by at most 1 β ). To make the above description more precise, let us recall that P B consists of (M1) single edges AB with both ends in N; (M2) paths ABCD with B, C ∈ N; and (M3) paths ABCDEF with B, C, D, E ∈ N.
Let us now analyse how the sets Q ∈ Q lying in edges or paths from (M1)-(M3) fill up when we embed small trees of typeT into them in the following specific ways. Clearly, the sets A, B of any edge as in (M1) will each get filled up with t vertices whenever we embed one tree of typeT in one 'direction' and a second tree of typeT in the other 'direction'.
The sets Q on paths ABCD as in (M2) will get filled as follows. If we • perform x rounds in which we embed one tree of the current typeT in the edge AB, with the root going to B; • perform x rounds in which we embed a tree of typeT in the edge CD, with the root going to C; • perform y rounds of embedding a tree of typeT with the root going to C, but the rest of the tree going to AB; and • perform y rounds of embedding a tree of typeT with the root going to B, but the rest of the tree going to CD, then after these 2x+2y rounds, A and D have received xt 2 +y(t 1 −1) vertices, while B and C have received xt 1 + y(t 2 + 1) vertices. So, if t 1 > t 2 (observe that then actually t 1 ≥ t 2 + 2, sinceT / ∈ T N earBal ), we will have the four sets A, B, C, D completely balanced out if we choose x = t 1 − t 2 − 2 and y = t 1 − t 2 . If t 2 ≥ t 1 , we can balance out the four clusters by taking x = t 2 − t 1 + 2 and y = t 2 − t 1 .
For the paths ABCDEF from (M3) we can calculate similarly: Say we do x rounds of embedding of a tree of typeT in the edge AB and another x rounds embedding it into EF . We then do y rounds of embedding the tree into AB, but with the roots of the tree going into C, and another y rounds putting it into EF , with the root going into D. Moreover, we perform 2z rounds where we embed the tree into CD, of which z rounds in each 'direction'. Then after these 2x + 2y + 2z rounds, we filled each of A and F with xt 2 + y(t 1 − 1) vertices, each of B and E with xt 1 + yt 2 vertices, and each of C and D with y + zt vertices.
Resuming all these observations, if t 1 > t 2 we can embed d := 2(t 1 − t 2 − 2)(t 1 − t 2 − 1)(t 1 − t 2 )t 2 · ((t − 1) · (t 1 − t 2 ) − t 1 ) trees of the current typeT , in a way that all sets Q ∈ Q will be used in a completely balanced way. If t 2 ≥ t 1 , we can embed d ′ := 2(t 2 − t 1 + 2)(t 2 − t 1 + 1)(t 2 − t 1 )t 2 · ((t − 1) · (t 2 − t 1 ) + t 1 ) trees of typeT , perfectly balancing all sets Q ∈ Q. Now, the number of trees of typeT might fail to be a multiple of d, or of d ′ , but, by putting some unused vertices into U ′ , we can finish the embedding of all the trees of the current type without any problems, perfectly balancing all Q ∈ Q.
Note that the number of vertices we add to U ′ when working on one tvertex tree from T U nbal is at most max{dt, d ′ t} ≤ 2t 8 ≤ 2 β 8 . So, the number of vertices we add to U ′ after working on all trees from T U nbal is at most the number of types of trees multiplied by 2 β 8 , and thus at most 2 β 10 . Phase 3. In the third phase of our embedding, we embed the trees from T N earBal . Note that each of these trees has at least one leaf in its heavier colour class. Instead of the root, as in phase 2, we will sometimes put the leaf into a different cluster, this time using the N-in-good path partition P A .
Easier calculations than in the previous case show that we can completely balance all slices C F 1 of clusters C ∈ V (M) if we embed six trees of typeT . So, putting at most 1 β 2 · 6 β ≤ 6 β 3 unused vertices into U ′ , we can finish the embedding of all the trees of T N earBal balancing all slices as desired.
After finishing Phase 3, we still put some more vertices into U ′ , before declaring the embedding procedure of the trees in T s ∩ F 1 finished. Namely, we put an appropiate number of vertices from the sets in X into U ′ . That is, the number of vertices from any of the sets of X we add to U ′ is the same as the number of vertices from any of the sets Q ∈ Q that went to U or to U ′ during the embedding of T s ∩ F 1 . This cleaning-up is only done because it will be nicer to be able to start the embedding of the trees at the next seed with all slices C F 1 perfectly balanced.
Observe that the number of vertices we added to U ′ while dealing with the trees from T s ∩ F 1 is at most 4 where we used (6) for the last inequality. Hence the bound (15) we had claimed above is correct. This ensures we have enough space for all future trees from F 1 .

Embedding the leaves
This section is devoted to the embedding of the leaves. That is, we are now at a stage where we have sucessfully embedded all seeds and all small trees, and all that is left to embed is L, the set of leaves adjacent to seeds. We will show we can embed all of L at once. If we cannot embed L into Z, then by Hall's theorem, there is some subset where L K is the set of leaves adjacent to elements of K, the set ϕ(K) is the set of images of K, and N(ϕ(K)) ∩ Z is the union of the neighbours in Z of the elements of ϕ(K).
Recall that by (E) from Subsection 6.2.3, we chose as the image of a seed s a vertex ϕ(s) that is typical with respect to C Z for almost all clusters C of R G . Because of (10), this means that each element of ϕ(K) sees at least ( In particular, by (11), each element of ϕ(K) sees more than 5 8 (|L| + 9 10 αm) vertices of Z. Thus, it follows that as otherwise 5 8 (|L| + 9 10 αm) ≥ |L|, which means that we could have embedded L without a problem.
Our aim is to reach a contradiction to the assumption that the set K exists. We will reach this contradiction by proving in Claims 6.2-6.6 that K misses a vertex in each of the large groups and also in most of the small groups of seeds we defined in Subsection 5.2.1. In some of the small groups K actually misses more than one vertex. We will prove these claims by repeatedly using (19).
This means that in total, K misses many vertices fromW , and these vertices spread out among the blocks (and thus have a corresponding proportion of the leaves hanging from them). Therefore, we can conclude that |L K | is smaller than the bound for the neighbourhood of ϕ(K) given in (20), and thus, L K could have been embedded without a problem, which is a contradiction.
Let us make this outline more precise. We start by proving that each of the large groups has a vertex outside K.
Claim 6.2. No large group is completely contained in K.
Proof. Assume otherwise, and consider the largest j for which there is a group of size 47 · 2 j completely contained in K. Then by Claim 6.1 (iv) from Subsection 6.2.4, we know that 1000 α ⌉, then by (11), this number exceeds |L|, which yields a contradiction to (19). So In particular, because of (7) and (8), we know that j < j * , and hence, there exists a large group of size 47 · 2 j+1 = 94 · 2 j . For any such group B, we know that, by the choice of j, there is a vertex v B ∈ B that is not in K. Let L B be the set of leaves adjacent to seeds in B, and let ℓ max (B) and ℓ min (B) be the number of leaves adjacent to the first and the last seed in B, respectively, under the size order σ. Thus, every seed b ∈ B is adjacent to a number ℓ b of leaves, with ℓ min (B Then Since the groups are consecutive in the size order, and since no seed has more than αm leaves adjacent to it, we know that So, the number of leaves adjacent to seeds that are not in K can be bounded by calculating Therefore, where the second and last inequalities follow from (11) and (22), respectively, and the third inequality follows from the observation that where for the first inequality we used that |Z| ≥ |L| > 3αm 2 (by (21)), and the second inequality follows from the facts that ε ≤ α 4 10 18 (by (5)) and j ≤ j ⊛ (by (23)). Now, inequality (24) gives a contradiction to (19). We have thus proved Claim 6.2.
Next, we will show that a similar statement holds for all small groups of size five. Claim 6.3. No small group of size 5 is completely contained in K.
Proof. Indeed, otherwise, because of Claim 6.1 (i), we know that Moreover, Claim 6.2 implies that every large group B of size 47 has a vertex v B which is not in K, and thus we can calculate, similar as above for Claim 6.2, that and thus, employing (11), we find that ) · (|Z| + α 4 10 6 m), which, with the help of (21) and (25), and using the fact that α ≫ ε, yields a contradiction to (19). This proves Claim 6.3.
Next, we turn to the groups of size four, separating the treatment of these into two cases depending on their type.
Claim 6.4. No small group of size 4 and of type 1 is completely contained in K.
Proof. Otherwise, because of Claim 6.1 (ii), we know that By Claim 6.3 we know that every group of size five has a vertex which is not in K. Hence, every large group B of size 47 contains at least two vertices v 1

B
and v 2 B that are not in K. Moreover, by the definition of the small groups, the first of these vertices, v 1 B , is one of the first 23 vertices of B under the size order, and the second vertex v 2 B , is one of the next 23 vertices of B under the size order.
So, we can split the group B minus its last vertex into two groups B 1 , B 2 containing the first 23 and the next 23 consecutive elements in the size order, respectively, with v 1 B ∈ B 1 and v 2 B ∈ B 2 . Defining dif (B 1 ), dif (B 2 ) as in Claim 6.2 for each of these two subgroups B 1 , B 2 of the group B of size 47, and letting ℓ v i B denote the number of leaves at v i B , for i = 1, 2, we can calculate that where L B 1 and L B 2 denote the sets of leaves adjacent to vertices from B 1 and B 2 , repectively. Thus, letting L B 3 denote the set of leaves adjacent to the very last vertex of the group B (of size 47), and noticing that |L B 3 | ≤ |L B | 47 , we can calculate that Therefore, using (11)  Proof. Otherwise, because of Claim 6.1 (iii), we know that However, by Claims 6.3 and 6.4, we know that every small group of size 5 and every small group of size 4 and of type 1 has a vertex which is not in K. So, we can split every large group B of size 47 into five subgroups B 1 , B 2 , B 3 , B 4 , B 5 , each consecutive in the size order, and with |B i | = 11 for i = 1, 2, 3, 4 and |B 5 | = 3, such that each of B 1 , B 2 , B 3 , B 4 contains a vertex v 1 B , v 2 B , v 3 B , v 4 B / ∈ K. Similar as above, we can calculate that where numbers ℓ v i B are defined as in the previous claim. Now, using (11) and (27), we obtain that |L K | ≤ 10 11 (|L| + αm) · (1 + 1 10 · 16 ) a contradiction to (19). This proves Claim 6.5.
Next, we will show that we can actually get some more out of the groups of type 2.
Claim 6.6. No small group of size 4 and of type 2 has three or more vertices in K.
Proof. Indeed, otherwise, because of the second part of Claim 6.1 (iii), we know that By Claims 6.3, 6.4 and 6.5, every small group, except possibly those of size one, has a vertex which is not in K. So, similar as in the previous claims, we can calculate that and then use (11) and (28), to obtain that a contradiction to (19). This proves Claim 6.6.
Resumingly, Claims 6.3-6.6 tell us that K misses at least one vertex of each small group of size four or five, and misses at least two vertices from each small group of size four and type 2. Recalling our ordering 4, 4, 4, 4, 5, 4, 4, 4, 4, 5, 4, 1 of the small groups inside each group B of size 47 as given in (4) in Subsection 5.2 (under ordering σ), we see that we can split B into five groups B 1 , B 2 , B 3 , B 4 , B 5 such that • for i = 1, 3, the group B i has 8 vertices, at least 3 of which are not in K; • for i = 2, 4, the group B i has 13 vertices, at least 5 of which are not in K; and • B 5 has 5 vertices, at least two of which are not in K.
Therefore, similarly as in the calculations for earlier claims, we can deduce that and thus by (11), we get a contradiction to (20). This means the Hall-obstruction K cannot exist, and we can thus finish the embedding of T by embedding all leaves from L in one step. This finishes the proof of Lemma 2.1.

Extending a given embedding
For the companion paper [RS19b], which proves the exact version of Theorem 1.4, we will need a second result, namely Lemma 7.3 below, apart from Lemma 2.1. Lemma 7.3 is actually very similar to Lemma 2.1. The difference is that in the context of [RS19b], we will be in a situation where a small tree T * is already embedded, except for a small but still considerably sized subset Q ⊆ V (T * ). Vertices in Q are very well chosen, and their neighbours in T * are embedded in very versatile vertices of G, which means we can leave the embedding of Q for later. Indeed, we will be able to embed vertices from Q into almost any leftover set of the right size. 5 So, we wish to embed T − T * , and we can count on extra free space of considerable size because of the not-yet-embedded set Q. This is very much like the situation we face in Lemma 2.1 (where we have free space because of the approximation), except that now, we have to cope with the already embedded T * − Q. However, as we will outline below, it is possible to adapt our proof of Lemma 2.1 to the new setting, with one possible exception. That is, if the graph G has a very specific structure (given in Definition 7.1 below), our embedding scheme will fail. The reason for it to fail is that we are not able to find the matchings M we need for the embedding of F 1 . It will be shown in [RS19b] how we can make use of the specific structure of G so that the tree can be embedded also in that case.
Another important point is that, for all proofs in [RS19b], we will count on a significant advantage. That is, we will be in a position to assume that none of the seeds from the cut-up of the tree has many leaves hanging from it. This will be crucial for our proof of Lemma 7.3, and it means that we can forget about all the extra work in the proof of Lemma 2.1 that was necessary for embedding the set L of leaves hanging from seeds.
In order to be able to properly state the result of this section, Lemma 7.3, we need two definitions. The first definition describes the structure of a graph to which the method from the present paper cannot be applied.
The next definition describes the already embedded subtree T * .
Definition 7.2 (γ-nice subtree). Let T be a tree with m edges. Call a subtree T * of T with root t * a γ-nice subtree if (i) |T * | < γm; and (ii) every component of T − T * is adjacent to t * .
We are now ready for the result we will need in [RS19b].
Lemma 7.3. For all γ < 1 10 6 there are m 0 ∈ N and λ > 0 such that the following holds for all m ≥ m 0 . Let G be an (m + 1)-vertex graph of minimum degree at least ⌊ 2m 3 ⌋ , which is not γ-special. Let T be a tree with m edges such that no vertex in T is adjacent to more than λm leaves. Let T * be a γ-nice subtree of T , with root t * , let Q ⊆ V (T * ) \ {t * }, and let S ⊆ V (G) with |S| ≤ |Q| − ( γ 2 ) 4 m. Suppose there is an embedding of T * − Q into G − S. Then there is an embedding of T − Q into G − S extending the embedding of T * − Q.
Proof. This proof follows the lines of the proof of Lemma 2.1. Note that the new difficulty is that we have to deal with the already embedded part of the tree T , and the unusable set S, together occupying up to almost γm vertices, which means that the usable degree of the other vertices might drop by almost γm (as they might see all of the used part of G). However, we have the advantage that we do not have to worry much about the leaves hanging from seeds, as there are very few.
Setting the constants. We start by setting the constants. Given γ, we note that we can count on an approximation factor of α := ( γ 2 ) 4 for the embedding of T − Q. We choose a suitable ε ≪ α, in particular, we will need that ε ≤ γ 20 .
Finally, we choose a sufficiently large m 0 for the output of Lemma 7.3. Resumingly, we will have that Now, assume we are given a graph G as in the lemma which is not γ-special, a set S, a tree T and a subtree T * of T , with |V (T * )| < γm, a vertex t * ∈ V (T * ), and a set Q ⊆ V (T * ) \ {t * }, such that there is an embedding of T * − Q into a set ϕ(V (T * ) − Q) ⊆ G − S, with t * embedded into ϕ(t * ).
Regularising the host graph. We regularise G ′ := G\(ϕ(V (T * −Q)∪S), obtaining a reduced graph R G ′ on p ′ vertices. Our plan is to extend the embedding of T * − Q to an embedding of all of T − Q into G − S. Recall that our main problem is that the minimum degree in R G ′ is no longer bounded from below by ( 2 3 −13ε)p, as it was in the proof of Lemma 2.1. Because of the possible degree into the set ϕ(V (T * − Q), we can only guarantee the following bound: Slicing up the clusters. After having embedded all trees from F * 1 , we go back to work in R G ′ . We slice up the yet unused parts of the clusters as before, into sets C Z , C W , CṼ , C F 1 \F * 1 , and C F 2 . The slices C X reflect the sizes of the corresponding sets X, but we leave sufficient buffer space in each (which we need for the same reasons as in the proof of Lemma 2.1, but also in order to deal with some new problems arising from having T * − Q already embedded).
We then go through the subtree induced by the seeds of (T − T * ) ∪ {t * } and the non-trivial trees hanging from them in a connected way (starting with the root t * ). We embed as usual each seed together with all small trees from F 1 ∪ F 2 hanging from it 6 , but leave out the leaves for later 7 . We always avoid the set C * R , unless we are about to embed a seed t ∈ R.
Embedding the seeds. We embed each seed s in a neighbour of the image ϕ(p(s)) of its parent p(s), and typical with respect to the slices C Z , CW , CṼ and C F 1 \F * 1 . Usually, seeds go to CW , but seeds t from R go to their reserved space C * R . Let us remark that we do not need to group and order our seeds as in the proof of Lemma 2.1, and we also do not need to choose the target clusters as carefully.
Embedding the trees from F 2 . These trees are easy to embed, because we can find the matching M F 2 just as before, and it does not matter that the minimum degree is only bounded by (32). In order to make the connections through the slices CṼ , for the vertices fromṼ , we only need to observe that every seed adjacent to trees from F ′ 2 is embedded in a vertex that is typical with respect to almost all slices CṼ .
Embedding the trees from F 1 \ F * 1 . As above, we slice up the clusters once more, so that almost all of the obtained slices behave uniformly with repect to being a neighbour or not of the image of the most recently embeded seed s. Let us call R ′′ G ′ the graph on these slices, after momentarily discarding those slices that are not of use to us.
Since G is not γ-special, we can find the perfect matchings M and good path partitions as in Lemmas 4.2 and 4.3 in R ′′ G ′ , in spite of only having condition (32). This can be shown exactly as above, when we embedded the trees from F * 1 . So we can embed the trees from F 1 \ F * 1 exactly as in the proof of Lemma 2.1.
Since the slices C Z are much larger than ε m p , and since the embedded seeds (except possibly t * ) see approximately two thirds of almost all of these slices, we have no problem to embed the leaves from L ′ greedily into C∈V (R G ′ ) C Z .