\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{amsthm,amsmath,amssymb} \usepackage{latexsym} \usepackage [dvips]{graphics} \usepackage{graphicx,epsfig} %\usepackage {pstcol} %\usepackage {pstricks,pst-node,pst-coil} %\usepackage{graphicx} \usepackage{epsfig} %%%%%%%%%%%% \newtheorem{thm}{Theorem} \newtheorem{cor}[thm]{Corollary} \newtheorem{pro}[thm]{Proposition} \newtheorem{lem}[thm]{Lemma} \newtheorem{cl}[thm]{Claim} \newtheorem{cj}[thm]{Conjecture} \newtheorem{rem}[thm]{Remark} \newtheorem{df}[thm]{Definition} \newcommand{\prf}{\noindent{\it Proof.} } \newcommand {\cbdo}{\hfill$\Box$} %\newcommand{\mod}{\ \def\mod{\mathop{\rm mod}\nolimits} \date{\dateline{Aug 18, 2015}{?, 2016}\\ \small Mathematics Subject Classifications: 05C35} \begin{document} \title{\bf On Erd\H{o}s-S\'os conjecture for trees of large size} \author{Agnieszka G\"orlich and Andrzej \.{Z}ak\thanks{The authors were partially supported by the Polish Ministry of Science and Higher Education.}\\ \small Faculty of Applied Mathematics \\ [-0.8ex] \small AGH University of Science and Technology \\ [-0.8ex] \small Krak\'ow, Poland\\ \small\tt forys@agh.edu.pl, zakandrz@agh.edu.pl} \maketitle \begin{abstract} Erd\H{o}s and S\'os conjectured that every graph $G$ of average degree greater than $k-1$ contains every tree of size $k$. Several results based upon the number of vertices in $G$ have been proved including the special cases where $G$ has exactly $k+1$ vertices (Zhou), $k+2$ vertices (Slater, Teo and Yap), $k+3$ vertices (Wo\'zniak) and $k+4$ vertices (Tiner). We further explore this direction. Given an arbitrary integer $c\geq 1$, we prove Erd\H{o}s-S\'os conjecture in the case when $G$ has $k+c$ vertices provided that $k\geq k_0(c)$ (here $k_0(c)=c^{12}{\rm polylog}(c)$). We also derive a corollary related to the Tree Packing Conjecture. \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} A set of (simple) graphs $G_1,G_2,\dots,G_q$ are said to \emph{pack into a complete graph} $K_n$ (in short pack) if $G_1,G_2,\dots,G_q$ can be found as pairwise edge-disjoint subgraphs in $K_n$. Many classical problems in Graph Theory can be stated as packing problems. In particular, $H$ is a subgraph of $G$ if and only if $H$ and the complement of $G$ pack. Erd\H{o}s and S\'os conjectured that every graph $G$ with average degree greater than $k-1$ contains every tree with $k$ edges. This conjecture has been restated by Wo\'zniak \cite{W2} as follows. \begin{cj}\label{cjES} Suppose that $G$ is a graph with $n$ vertices and $T$ is any tree with $k$ edges. If $|E(G)|<\frac{n(n-k)}{2}$, then $G$ and $T$ pack (into the complete graph $K_n$). \end{cj} Recently, Ajtai, Koml\'os, Simonovits and Szemer\'edi proved Conjecture \ref{cjES} for sufficiently large $k$, see \cite{AKSS}. Since they used the Szemer\'edi regularity lemma the term 'suficiently large' means huge. There are also many partial results concerning this conjecture. They have been obtained either for some special families of graphs \cite{BD,Dob,ET,W} or for some special families of trees \cite{FS,ML,Sid} or else for certain values of the parameters $k$ and $n$. In particular, the cases where $n$ is equal to $k+1$, $k+2$, $k+3$, or $k+4$ were proved by Zhou \cite{Zhou}, by Slater, Teo, and Yap \cite{STY}, by Wo\'zniak \cite{W2}, and by Tiner \cite{Tin}, respectively. We extend these results to $n=k+c$ for any $c$, provided $k$ is sufficiently large. \begin{thm}\label{ES} Let $c$ be a positive integer and let $k_0(c)=\gamma c^{12}\ln^4c$ where $\gamma$ is some universal sufficiently large constant. Then for every $t=1,\dots,c$ and for every integer $k\geq k_0(c)$ the following holds. If $T$ is a tree with $k$ edges and $G$ is a graph on $k+t$ vertices with $|E(G)|< \frac{t(k+t)}{2}$, then $T$ and $G$ pack into $K_{k+t}$. \end{thm} Another famous tree packing conjecture (TPC) posed by Gy\'arf\'as \cite{Gya} states that any set of $n-1$ trees $T_n,T_{n-1},\dots,T_2$ such that $T_i$ has $i$ vertices pack into $K_n$. In \cite{Bol2} Bollob\'as suggested the following weakening of TPC \begin{cj} For every $c\geq 1$ there is an $n(c)$ such that if $n\geq n(c)$, then any set of $c$ trees $T_1,T_2,\dots,T_c$ such that $T_i$ has $n-(i-1)$ vertices pack into $K_n$. \end{cj} Bourgeois, Hobbs and Kasiraj \cite{HBK} showed that any three trees $T_n$, $T_{n-1}$, $T_{n-2}$ pack into $K_n$. Recently, Balogh and Palmer \cite{BP} proved that any set of $t=\frac{1}{10}n^{1/4}$ trees $T_1,\dots, T_t$ such that no tree is a star and $T_i$ has $n-i+1$ vertices pack into $K_n$. We obtain the following corollary of Theorem \ref{ES}: \begin{cor}\label{packtrees} Let $c$ be a positive integer and let $n_0(c)=\gamma c^{12}\ln^4c$ where $\gamma$ is some universal sufficiently large constant. If $n\geq n_0(c)$, then any set of $c$ trees $T_1,T_2,\dots, T_c$, such that $T_i$ has $n-2(i-1)$ vertices pack into $K_n$. \end{cor} \prf The proof is by induction on $c$. For $c=1$ the statement is obvious. So fix some $c>1$ and assume that the statement is true for $c-1$. Let $T_1,T_2,\dots,T_c$ be any set of $c$ trees such that $T_i$ has $n-2(i-1)$ vertices. By the induction hypothesis $T_1,T_2,\dots,T_{c-1}$ pack into $K_n$. Let $G$ be a graph with $V(G)=V(K_n)$ and $E(G)=\bigcup_{i=1}^{c-1}E(T_i)$. Clearly, \[|E(G)|\leq (c-1)n< \frac{(2c-1)n}{2}.\] Furthermore, $T_c$ has $n-(2c-1)$ edges. Thus, by Theorem \ref{ES}, $G$ and $T_c$ pack, which completes the proof of the corollary.\cbdo The notation is standard. In particular $|V(G)|$ is called the order of $G$ and $|E(G)|$ is called the size of $G$. Furthermore, $d_G(v)$ (abbreviated to $d(v)$ if no confusion arises) denotes the degree of a vertex $v$ in $G$, $\delta(G)$ and $\Delta(G)$ denote the minimum and the maximum degree of $G$, respectively. $N_G(v)$ denotes the set of neighbors of $v$ and, for a subset of vertices $W$, $N_G(W)=\bigcup_{w\in W}N(w)\setminus W$ and $N_G[W]=N_G(W)\cup W$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Preliminaries} In the proof we refine the approach of Alon and Yuster from \cite{AY}. However, we apply it in a slightly different way as we choose random subsets $B_i$ (to be defined later) in a denser graph. We write Bin$(p,n)$ for the binomial distribution with $n$ trials and success probability $p$. Let $X\in {\rm Bin}(n,p)$. We will use the following two versions of the Chernoff bound which follows from formulas (2.5) and (2.6) from \cite{JLR} by taking $t=2\mu-np$ and $t=np-\mu/2$, respectively. If $\mu \geq E[X]=np$ then \begin{align}\label{chernoff1} Pr[X\geq 2\mu]\leq {\rm exp}(-\mu/3) \end{align} On the other hand, if $\mu \leq E[X]=np$ then \begin{align}\label{chernoff2} Pr[X\leq \mu/2]\leq {\rm exp}(-\mu/8). \end{align} \begin{pro}\label{ity} Let $G$ be a graph with $n$ vertices and at most $m$ edges. Let $V(G)=\{v_1,\dots,v_n\}$ with $d(v_1)\geq d(v_2)\geq \cdots\geq d(v_n)$. Then \[d(v_i)\leq \frac{2m}{i}.\] \end{pro} \prf The proposition is true because \[2m\geq \sum_{j=1}^{n}d(v_j)\geq \sum_{j=1}^id(v_j)\geq id(v_i).\]\cbdo The following technical lemma is the main tool in the proof. A version of it appeared in \cite{AY}. \begin{lem}\label{cidi} Let $G$ be a graph with $n$ vertices and at most $m$ edges. Let $V(G)=\{v_1,\dots,v_n\}$ with $d(v_1)\geq d(v_2) \geq \cdots \geq d(v_n)$. Let $A_i$, $i=1,\dots,n$, be any subsets of $V(G)$ with the additional requirement that if $u\in A_i$ then $d(u)< a$. For $i=1,\dots,n$ let $B_i$ be a random subset of $A_i$ where each vertex of $A_i$ is independently selected to $B_i$ with probability $p<1/a$. Let \begin{align*} &C_i=\left( \bigcup_{j=1}^{i-1}B_j\right)\cap N(v_i),\\ &D_i=B_i\setminus \left( \bigcup_{j=1}^{i-1}N[B_j]\right). \end{align*} \noindent Then 1. $Pr\left[|C_i|\geq 4mp\right]\leq \exp(-2mp/3)$ for $i=1,\dots,n$ 2. $Pr\left[|D_i|\leq \frac{p|A_i|}{2e}\right]\leq \exp\left( \frac{-p|A_i|}{8e}\right)$ for $i=1,\dots,\lfloor 1/(ap)\rfloor$. \end{lem} \prf Fix some vertex $v_i\in V(G)$. Consider the first part of the lemma. If $d(v_i)\leq 2mp$ then the probability is zero because $|C_i|\leq |N(v_i)|=d(v_i)$. So we may assume that $d(v_i)> 2mp$. For $u \in N(v_i)$ the probability that $u\in B_j$ is at most $p$ (it is either $p$ if $u\in A_j$ or 0 if $u\not\in A_j$.) Thus $Pr[u\in C_i]\leq(i-1)p$. By Proposition \ref{ity}, $i \leq 2m/d(v_i)$. Hence, \[ Pr[u\in C_i]\leq \frac{2mp}{d(v_i)}.\] Observe that $|C_i|$ is a sum of $d(v_i)$ independent indicator random variables each of which has success probability at most $\frac{2mp}{d(v_i)}$. Thus, the expectation of $|C_i|$ is at most $2mp$. Therefore, by (\ref{chernoff1}), the probability of $|C_i|$ being larger than $4mp$ satisfies \begin{align*} Pr[|C_i|\geq 4mp]\leq {\rm exp}\left( -2mp/3\right). \end{align*} Consider now the second part of the lemma. Observe that for $u\in A_i$, the probability that $u\in B_i$ is $p$. On the other hand, for any $j$, the probability that $u\not\in N[B_j]$ is at least $1-ap$. Indeed, $u\in N[B_j]$ if and only if $u\in B_j$ or one of its neighbors belongs to $B_j$. Since $u\in A_i$, it has at most $a-1$ neighbors. Hence, the probability that $u \in N[B_j]$ is at most $ap$. Therefore, as long as $i\leq 1/(ap)$, \[Pr[u\in D_i]\geq p(1-ap)^{i-1}\geq \frac{p}{e}.\] Observe that $|D_i|$ is a sum of $|A_i|$ independent indicator random variables, each having success probability at least $\frac{p}{e}$. Therefore the expectation of $|D_i|$ is at least $ \frac{p|A_i|}{e}$. By (\ref{chernoff2}), the probability that $|D_i|$ falls below $\frac{p|A_i|}{2e}$ satisfies \begin{align*} Pr\left[|D_i|\leq \frac{p|A_i|}{2e}\right]\leq {\rm exp}\left( -\frac{p|A_i|}{8e}\right). \end{align*} \cbdo \section{ Proof of Theorem \ref{ES}.} The proof is by induction on $t$. By Zhou's result the theorem holds for $t=1$. So fix some $t$, $2\leq t\leq c$, and assume that the statement is true for $t-1$. Let $G'$ be a (bipartite) graph that arises from $T$ by adding a set $I'$ of $t-1$ isolated vertices. Thus $|V(G)|=|V(G')|$. Clearly, $G'$ and ${G}$ pack if and only if $T$ and ${G}$ pack. Let $V(G)=\{v_1,\dots,v_n\}$ where $d_G(v_i)\geq d_G(v_{i+1})$ and $V(G')= \{v'_1,\dots,v'_n\}$ where $d_{G'}(v'_i)\geq d_{G'}(v'_{i+1})$. Since $|E(G)|2|E(G)|=\sum_{i=1}^{n}d(v_i)\geq \alpha \cdot 5c,\] and so $\alpha\leq \frac{ n}{5}$. Therefore \[|S_i|\geq k/2-\frac{n}{5}\geq n/4+t.\]\cbdo \\ Now, we divide the proof into two cases depending whether $\Delta(T)< 60cn^{3/4}$ or $\Delta(T)\geq 60cn^{3/4}$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Case $\Delta(T)< 60cn^{3/4}$} Recall that $S_i\subset V(G)\setminus N[v_i]$ with the assumption that if $u\in S_i$ then $d_G(u)< 5c$. For $i=1,\dots,n$ let $B_i$ be a random subset of $S_i$ where each vertex of $S_i$ is independently selected to $B_i$ with probability \begin{align}\label{pe} p=\frac{n^{-3/4}}{15\cdot10^2c^3} \end{align} Let \begin{align*} &C_i=\left( \bigcup_{j=1}^{i-1}B_j\right)\cap N(v_i),\\ &D_i=B_i\setminus \left( \bigcup_{j=1}^{i-1}N[B_j]\right). \end{align*} \begin{cl}\label{cidi3} The following conditions hold simultaneously with positive probability: 1. $|C_i|\leq \frac{n^{1/4}}{750c^2}$ for $i=1,\dots,n$ 2. $|D_i|\geq 3$ for $i=1,\dots,\lfloor300c^2n^{3/4}\rfloor$. \end{cl} \prf Recall that $|E(G)|<\frac{tn}{2}\leq \frac{cn}{2}$. Thus, by Lemma \ref{cidi}, \[Pr\left[ |C_i|\geq \frac{n^{1/4}}{750c^2}\right]\leq {\rm exp}\left(\frac{-n^{1/4}}{4500c^2}\right)<\frac{1}{2n}.\] Furthermore, by Claim \ref{sinowe}, \[3\leq \frac{n^{1/4}}{12\cdot10^3ec^3}=\frac{n^{-3/4}\cdot(n/4)}{15\cdot 10^2c^3\cdot2e}<\frac{p|S_i|}{2e}.\] Hence, by Lemma \ref{cidi} (with $a=5c$ and $A_i=S_i$), for each $i\leq \lfloor1/(ap)\rfloor=\lfloor 300c^2n^{3/4}\rfloor$ \begin{align*}Pr[|D_i|\leq 3]&\leq Pr\left[|D_i|\leq \frac{p|S_i|}{2e} \right]\leq \exp\left(- \frac{p|S_i|}{8e}\right)\\ &\leq \exp\left(-\frac{n^{1/4}}{48\cdot10^3ec^3}\right)< \frac{1}{600c^2n^{3/4}}. \end{align*} Thus, by the union bound, each part of the lemma holds with probability greater than $1/2$. Hence both hold with positive probability.\cbdo Therefore, we may fix sets $B_1,\dots,B_n$ satisfying all the conditions of Claim \ref{cidi3} with respect to the cardinalities of the sets $C_i$ and $D_i$. We construct a packing $f:V(G)\rightarrow V(G')$ in three stages. At each point of the construction, some vertices of $V(G)$ are \emph{matched} to some vertices of $V(G')$, while the other vertices of $V(G)$ and $V(G')$ are yet unmatched. Initially, all vertices are unmatched. We always maintain the packing property, that is for any $u,v\in V(G)$ if $uv\in E(G)$ then $f(u)f(v)\not\in E(G')$. In Stage 1 we match certain number of vertices of $G$ that have the largest degrees. After this stage, by the assumption that $\Delta(G')\leq 60cn^{3/4}$, both $G$ and $G'$ do not have unmatched vertices of high degree (vertices of high degree are the main obstacle in packing). This fact enables us to complete the packing in Stages 2 and 3. \emph{Stage 1} Let $x$ be the largest integer such that $d_G(v_x)\geq \frac{n^{1/4}}{300c}$. Thus, by Proposition \ref{ity}, \begin{align}\label{ix2} x\leq 300c^2{n}^{3/4} \end{align} This stage is done repeatedly for $i=1,\dots, x$ and throughout it we maintain the following two invariants \begin{enumerate} \item At iteration $i$ we match $v_i$ with some vertex $f(v_i)$ of $G'$ such that $d_{G'}\left( f(v_i)\right)\leq 3$. \item Furthermore, we match all yet unmatched neighbors of $f(v_i)$ to some vertices of $B_i$ (this way all neighbors of $f(v_i)$ in $G'$ are matched to vertices of $\bigcup_{j=1}^iB_j$). \end{enumerate} To see that this is possible, consider the i'th iteration of Stage 1 where $v_i$ is some yet unmatched vertex of $G$. Let $Q'$ be the set of all yet unmatched vertices of $G'$ having degree less than or equal to 3. Note that, by Proposition \ref{ity}, the number of vertices of degree less than or equal to 3 in $G'$ is at least $n/2$. Hence, \[|Q'|\geq n/2-4(i-1)\geq n/2-4x\geq n/2-1200c^2{n}^{3/4}\geq n/3.\] Let $X$ be the set of already matched neighbors of $v_i$ and let $Y'=N_{G'}(f(X))$. Thus, the valid choice for $f(v_i)$ would be a vertex of $Q'\setminus Y'$. To see that such a choice is possible, it is enough to show that $|Q'|>|Y'|$. Let $X=X_1\cup X_2$ with $X_1\subseteq \{v_1,\dots,v_{i-1}\}$ and $X_2\subseteq B_1\cup \cdots \cup B_{i-1}$. Hence $X_1\leq x$ and $|X_2|=|C_i|$. Thus, by the first invariant of Stage 1, and by (\ref{ix2}) and Claim \ref{cidi3} \begin{align*} |Q'|-|Y'|&\geq n/3-3|X_1|-\Delta(G')|X_2|\geq n/3-3x-60c{n}^{3/4}|C_i|\\ &\geq n/3-900c^2{n}^{3/4}-60c{n}^{3/4}\frac{{n}^{1/4}}{750c^2}\\ &=n/3-6n/(75c)-900c^2n^{3/4}> n/4-900c^2n^{3/4}>0. \end{align*} In order to maintain the second invariant it remains to match the yet unmatched neighbors of $f(v_i)$ with vertices from $B_i$. Let $R'$ be the set of neighbors of $f(v_i)$ in $G'$ that are still unmatched. Recall that $|R'|\leq 3$. We have to match vertices of $R'$ with some vertices of $B_i$. Since $D_i=B_i\setminus \left( \bigcup_{j=1}^{i-1}N[B_j]\right)$, a valid choice of such vertices is by taking an $|R'|$-subset of $D_i$. By Claim \ref{cidi3} and by (\ref{ix2}), $|D_i|\geq 3$ for $i=1,\dots,x$. Furthermore, since each $v\in D_i$ satisfies $d_G(v)<5c\leq d_G(v_x)$, $D_i\cap \{v_1,\dots,v_{i-1}\}=\emptyset$. Thus, all vertices of $D_i$ are still unmatched. Hence, such a choice is possible. \emph{Stage 2} Let $M_1$ and $M'_1$ be the set of matched vertices of $G$ and $G'$ after Stage 1, respectively. Clearly $|M_1|=|M'_1|\leq 4x< n/9$. Hence $G'- M'_1$ has an independent set $J'$ with $|J'|\geq 4n/9$. In Stage 2 we match the vertices from $V(G')\setminus(M'_1\cup J')$, one by one, with some $n-|M_1|-|J'|$ vertices from $V(G)\setminus M_1$. Suppose that $v'\in V(G')\setminus (M'_1\cup J')$ is still unmatched. Let $Q$ be the set of all yet unmatched vertices of $G$. Clearly, $|Q|\geq |J'|\geq 4n/9$ since the vertices of $J'$ remain unmatched in every step of Stage 2. Let $X'$ be the set of already matched neighbors of $v'$. Let $Y=N_{G}(f^{-1}(X'))$. Thus, the valid choice for $f^{-1}(v')$ would be a vertex of $Q\setminus Y$. To see that such a choice is possible we will prove that $|Q\setminus Y|>0$. \\ Recall that \[|X'|\leq 60c{n}^{3/4}.\] What is more, by the second invariant of Stage 1, the neighbors of each $f(v_i)$, $i=1,\dots,x$, are already matched. Hence, \[X'\subset V(G')\setminus\{f(v_1),\dots,f(v_x)\}\] and so \[f^{-1}(X')\subset V(G)\setminus\{v_1,\dots,v_x\}.\] Thus, by the definition of $x$, for each $u'\in X'$ we have \begin{align}\label{rev1} \left|N_{G}(f^{-1}(u'))\right|\leq \frac{{n}^{1/4}}{300c}. \end{align} Therefore, \begin{align*} |Q\setminus Y|\geq |Q|-|X'|\frac{{n}^{1/4}}{300c}\geq 4n/9-60c{n}^{3/4}\frac{{n}^{1/4}}{300c}>0. \end{align*} \emph{Stage 3} Let $M_2$ and $M'_2$ be the sets of matched vertices of $G$ and $G'$ after Stage 2, respectively. In order to complete a packing of $G$ and $G'$, it remains to match the vertices of $V(G)\setminus M_2$ with the vertices of $J'$. Consider a bipartite graph $B$ whose sides are $V(G)\setminus M_2$ and $J'$. For two vertices $u\in V(G)\setminus M_2$ and $v'\in J'$, we place an edge $uv'\in E(B)$ if and only if it is possible to match $u$ with $v'$ (by this we mean that mapping $u$ to $v'$ will not violate the packing property). Thus $u$ is not allowed to be matched to at most $d_G(u)\Delta(G')$ vertices of $J'$. Hence \[d_B(u)\geq |J'|-\frac{{n}^{1/4}}{300c}60c{n}^{3/4}> |J'|-2n/9\geq |J'|/2.\] Now we will evaluate $d_B(v')$. We define $X'$ and $Y$ in the same way as in Stage 2. Then (\ref{rev1}) holds again. Hence, $v'$ is not allowed to be matched to at most $\Delta(G')\frac{{n}^{1/4}}{300c}$ vertices of $V(G)\setminus M_2$. Thus, \[d_B(v')\geq |J'|-\frac{{n}^{1/4}}{300c}60c{n}^{3/4}\geq |J'|/2.\] Therefore, by Hall's Theorem there is a perfect matching in $B$, and so a packing of $G$ and $G'$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Case $\Delta(T)\geq 60c{n}^{3/4}$} In this case we will follow the ideas from the previous subsection. However, the key difference is that now both $G$ and $G'$ may have vertices of high degrees. Because of this obstacle, a packing has two more stages at the beginning. After a preparatory Stage 1, in Stage 2 we match the vertices of $G$ that have high degrees with vertices of $G'$ that have small degrees. Then in Stage 3, we match the vertices of $G'$ having high degree. This stage is very similar to Stage 1 from the previous subsection, but with the change of the role of $G$ and $G'$. Finally, we complete the packing in Stages 4 and 5, which are analogous to Stages 2 and 3 from the previous subsection. Let \begin{align}\label{defku} q=\frac{{n}^{1/4}}{59c}. \end{align} Let $P'\subseteq N_{G'}(v'_1)$ be the set of neighbors of $v'_1$ such that each vertex in $P'$ has degree at most $q$ in $G'$, and every neighbor different from $v'_1$ of every vertex from $P'$ has degree at most $q$ in $G'$. \begin{cl} $|P'|> c{n}^{3/4}$. \end{cl} \prf Note that every vertex $v'\in N_{G'}(v'_1)\setminus P'$ has the property that $d_{G'}(v')>q$ or $v'$ has a neighbor $w'\neq v'_1$ such that $d_{G'}(w')> q$. Therefore, \[n=|V(G')|> (\Delta(G')-|P'|)q\geq (60c{n}^{3/4}-|P'|)\frac{{n}^{1/4}}{59c},\] and the statement follows. \cbdo \\ We construct a packing $f:V(G)\rightarrow V(G')$ in five stages. At each point of the construction, some vertices of $V(G)$ are \emph{matched} to some vertices of $V(G')$, while the other vertices of $V(G)$ and $V(G')$ are yet unmatched. Initially, all vertices are unmatched. \emph{Stage 1}. We first match $v_n$ with $v'_1$, i.e. $f(v_n)=v'_1$. Next we match the neighbors of $v_n$ with $d_G(v_n)$ vertices from $I'$. This is possible since, by (\ref{delta}), $d_G(v_n)=\delta(G)\leq t-1=|I'|$. Moreover, since $I'$ is a set of isolated vertices, this maping does not violate the packing property. \emph{Stage 2}. Let $z$ be the largest integer such that $d_G(v_z)\geq {{n}^{1/4}}$. Since $|E(G)| q-1.\] Hence, this is possible. Before we describe Stage 3, we need some preparations. Let $M_2$ be the set of all vertices of $G$ that were matched in Stage 1 or 2. Similarly, let $M'_2$ be the set of all vertices of $G'$ that were matched in Stage 1 or 2. Recall that \begin{align}\label{after2} |M_2|=|M'_2|\leq t+zq\leq t+n/59. \end{align} Let $H=G[V\setminus M_2]$ be a subgraph of $G$ induced by yet unmatched vertices. Similarly let $H'=G'[V'\setminus M'_2]$. Note that since $G'$ is acyclic and by the construction of Stages 1 and 2, \begin{align}\label{stopienwh'} &d_{G'}(v')\leq d_{H'}(v')+1 \text{ for each } v'\in V'\setminus M'_2. \end{align} Let $V(H')=\{w'_1,\dots,w'_r\}$ with $d_{H'}(w'_1)\geq d_{H'}(w'_2)\geq \cdots \geq d_{H'}(w'_r)$. By (\ref{after2}), \begin{align}\label{er} r\geq n-(t+n/59)>3n/4. \end{align} Let $y$ be the largest integer such that $d_{H'}(w'_y)\geq 360\sqrt{n}$. Then, by Proposition \ref{ity}, \begin{align}\label{igrek} y\leq \frac{2n}{360\sqrt{n}}=\frac{\sqrt{n}}{180}. \end{align} For each $1\leq i \leq r$ we define a set $S'_i\subseteq V(H')\setminus N_{H'}[w'_i]$ to be a largest independent set of vertices but with the additional requirement that each $w' \in S'_i$ has $d_{H'}(w')< 180$. \begin{cl}\label{siprim} $|S'_i|\geq n/10$ for $i\geq 1$. \end{cl} \prf Note that each $w'_i$ has at least \[r-d_{H'}(w'_i)-1\geq r-d_{G'}(w'_i)-1\geq r-d_{G'}(v'_2)-1\geq r-\frac{n}{2}-1\geq \frac{3}{4}n-\frac{n}{2}-1 =\frac{n}{4}-1\] non-neighbors. Since $H'$ is a forest, the subgraph of $H'$ induced by all non-neighbors of $w'_i$ has an independent set of cardinality at least $\frac{n/4-1}{2}>n/9$. Let $\alpha$ be the number of vertices of $H'$ that have degree greater than or equal to $180$. Thus \[ 2n>\sum_{j=1}^{r}d_{H'}(w'_j)\geq \alpha \cdot 180,\] and so $\alpha\leq \frac{n}{90}$. Therefore \[|S'_i|\geq n/9-\frac{n}{90}= n/10.\] \cbdo For $i=1,\dots,r$ let $B'_i$ be a random subset of $S'_i$ where each vertex of $S'_i$ is independently selected to $B'_i$ with probability $1/\sqrt{n}$. Let \begin{align*} &C'_i=\left( \bigcup_{j=1}^{i-1}B'_j\right)\cap N(w'_i),\\ &D'_i=B'_i\setminus \left( \bigcup_{j=1}^{i-1}N_{H'}[B'_j]\right). \end{align*} \begin{cl}\label{cidi2} The following conditions hold simultaneously with positive probability: 1. $|C'_i|\leq 4\sqrt{n}$ for $i=1,\dots,r$ 2. $|D'_i|\geq \frac{\sqrt{n}}{20e}$ for $i=1,\dots,y$. \end{cl} \prf Clearly, $|E(H')|< n$. By Lemma \ref{cidi} (with $m=n$, $p=1/\sqrt{n}$ and $A_i=S'_i$ and $a=180$), \begin{align*} &Pr\left[|C'_i|\geq 4\sqrt{n}\right]\leq \exp(-2\sqrt{n}/3)< \frac{1}{2n}\leq \frac{1}{2r}. \end{align*} Furthermore, by Claim \ref{siprim}, \[ \frac{\sqrt{n}}{20e}=\frac{(1/\sqrt{n})(n/10)}{2e}\leq\frac{p|S'_i|}{2e}.\] Hence, by the second part of Lemma \ref{cidi} and by (\ref{igrek}), for $i\leq y\leq \lfloor\sqrt{n}/180\rfloor$ we have \begin{align*} Pr\left[|D'_i|\leq \frac{\sqrt{n}}{20e}\right]&\leq Pr\left[|D'_i|\leq \frac{p|S'_i|}{2e}\right]\leq{\rm exp}\left(-\frac{p|S'_i|}{8e}\right)\\ &\leq \exp\left(-\frac{(1/\sqrt{n})(n/10)}{8e}\right)= \exp\left(-\frac{\sqrt{n}}{80e}\right)<\frac{90}{\sqrt{n}}\leq \frac{1}{2y}. \end{align*} Thus, by the union bound, each part of the lemma holds with probability greater than $1/2$. Hence both hold with positive probability. \cbdo Now we are in the position to describe the next stages of a packing. By Claim \ref{cidi2} we may fix independent sets $B'_1,\dots,B'_r$ satisfying all the conditions of Claim \ref{cidi2} with respect to the cardinalities of the sets $C'_i$ and $D'_i$. Let $W=\{v_1,\dots,v_z\}$. Recall that \begin{align}\label{deltawu} \Delta(G-W)<{{n}^{1/4}}. \end{align} \emph{Stage 3} This stage is done repeatedly for $i=1,\dots,y$ and throughout it we maintain the following (similar to those from Stage 2) invariants \begin{enumerate} \item At iteration $i$ we match $w'_i\in V(H')$ with some yet unmatched vertex $u=f^{-1}(w'_i)$ of $H$ such that $d_G(u)\leq 2c$. \item Furthermore, we match all yet unmatched neighbors in $H$ of $f^{-1}(w'_i)$ to vertices of $B'_i$ (this way all neighbors of $f^{-1}(w'_i)$ in $H$ are matched to vertices of $\bigcup_{j=1}^iB'_j$). \end{enumerate} To see that this is possible, consider the i'th iteration of Stage 3 where $w'_i$ is some yet unmatched vertex of $H'$. Let $Q$ be the set of all yet unmatched vertices of $G$ having degree less than or equal to $2t$. Note that, by Proposition \ref{ity}, the number of vertices of degree less than or equal to $2t$ in $G$ is at least $n/2$. Hence, by (\ref{after2}) and (\ref{igrek}), and since $t\leq c$, \begin{align}\label{ku} |Q|&\geq n/2-|M_2|-2ty\geq n/2-t-n/59-c\sqrt{n}/90>n/4. \end{align} Let $X'$ be the set of already matched neighbors (in $G'$) of $w'_i$ and let $Y=N_{G}(f^{-1}(X'))$. Thus, the valid choice for $f^{-1}(w'_i)$ would be a vertex of $Q\setminus Y$. Let $X'=X'_1\cup X'_2\cup X'_3$ such that $X'_1\subset M'_2=V(G')\setminus V(H')$, $X'_2\subset \{w'_1,\dots,w'_{i-1}\}$ and $X'_3\subset \bigcup_{j=1}^{i-1}B'_i$. By (\ref{stopienwh'}), $|X'_1|\leq 1$. Moreover if $v'\in X'_1$ then, by the second invariant of Stage 2, $v'\not\in N_{G'}(v'_1)$. Thus $v'=v'_1$ or $v'$ is at distance 2 from $v'_1$. Hence, either $f^{-1}(v')=v_n$ or $f^{-1}(v')$ belongs to some set $S_j$, $j\in \{1,\dots,z\}$. Therefore, $d_G\left(f^{-1}(v')\right)\leq 5c$. Furthermore, $|X'_2|\leq i-1$ and, by Claim \ref{cidi2}, $|X'_3|\leq 4 \sqrt{n}$. Hence, by (\ref{deltawu}) and by the first invariant of Stage 3, \begin{align} |Y|&\leq 5c|X'_1|+2c|X'_2|+|X'_3|\cdot{{n}^{1/4}} 0.$ In order to maintain the second invariant we have to match yet unmatched neighbors of $f^{-1}(w'_i)$ with some vertices of $B'_i$. Let $R$ be the set of neighbors of $f^{-1}(w'_i)$ in $G$ that are still unmatched. Recall that by the first invariant (of Stage 3) $|R|\leq 2c$. Since $D'_i=B'_i\setminus \left( \bigcup_{j=1}^{i-1}N[B'_j]\right)$, a natural choice of such vertices is taking an $|R|$-subset of $D'_i$. However, unlike in Stage 1 in the previous subsection, this subset cannot be chosen arbitrarily because of the existence of possible edges between vertices from $P'':=N_{G'}(P')\setminus \{v'_1\}$ and $D'_i$. For this reason, we have to match the vertices from $R$ carefully. We match them, one by one, with some vertices from $D'_i$ in the following way. Suppose that $v\in R$ is yet unmatched. Let $D'$ be the set of yet unmatched vertices of $D'_i$. Since each $w'\in D'_i$ satisfies $d_{H'}(w')<180\leq 360\sqrt{n}$, $D'_i\cap\{w'_1,\dots,w'_{i-1}\}=\emptyset$. Hence, \begin{align}\label{debis} |D'|\geq |D'_i|-|R|\geq {\sqrt{n}}/(20e)-2c. \end{align} Let $X_2$ be the set of those already matched neighbors $u$ of $v\in R$ which satisfy $f(u)\in P''$. Let $Y'_2=N_{G'}(f(X_2))$. Thus, the valid choice for $f(v)$ would be a vertex from $D'\setminus Y'_2$. Recall, that by the definition of $z$, $|X_2|\leq d_G(v)\leq n^{1/4}$. Furthermore, by the definition of $P'$, $N_{G'}(f(u))\leq q$. Thus, by (\ref{defku}) and (\ref{debis}), \begin{align*} |D'\setminus Y'_2|>\sqrt{n}/(20e)-2c-\sqrt{n}/59>0. \end{align*} Thus, an appropriate choice for $f(v)$ is possible. \emph{Stage 4} Let $M_3$ be the set of matched vertices of $G$ after Stage 3. Similarly, let $M'_3$ be the set of matched vertices of $G'$ after Stage 3. Note that, by (\ref{igrek}) and (\ref{after2}), \begin{align}\label{after3} |M_3|=|M'_3|\leq |M_2|+(2c+1)y\leq t+n/59+(2c+1)\sqrt{n}/1800,\] and so the choice for $f^{-1}(v')$ is possible. \emph{Stage 5} Let $M_4$ and $M'_4$ be the sets of matched vertices of $G$ and $G'$, respectively, after Stage 4. In order to complete a packing of $G$ and $G'$ it remains to match the vertices of $J'$ with the yet unmatched vertices of $G$. Consider a bipartite graph $B$ whose sides are $V(G)\setminus M_4$ and $J'$. For two vertices $u\in V(G)\setminus M_4$ and $v'\in J'$, we place an edge $uv'\in E(B)$ if and only if it is possible to match $u$ with $v'$ (by this we mean that mapping $u$ to $v'$ will not violate the packing property). Recall that, by (\ref{deltawu}), $d_G(u)\leq {n}^{1/4}$. Moreover, by the construction of Stage 1 and by the second invariant of Stage 3, $f(N_G(u))\subset V(G')\setminus W'$. Thus, by (\ref{deltawu'}), $u$ is not allowed to be matched to at most $n^{1/4}\left(360\sqrt{n}+1\right)$ vertices of $J'$. Therefore, \begin{align*} d_B(u)\geq |J'|-{n}^{1/4}\left(360\sqrt{n}+1\right) > |J'|-3n/16\geq|J'|/2. \end{align*} Similarly, by (\ref{deltawu'}), $d_{G'}(v')\leq 360\sqrt{n}+1$. Moreover, by the second invariant of Stage 2, $f^{-1}(N_{G'}[v'])\subset V(G)\setminus W$. Therefore, by (\ref{deltawu}), \[d_B(v')\geq |J'|-{n}^{1/4}\left(360\sqrt{n}+1\right)>|J'|/2.\] Therefore, by Hall's Theorem there is a perfect matching in $B$, and so a packing of $G$ and $G'$. This completes the inductive step, and so the theorem is proved. \cbdo \section{Acknowledgements} We thank the reviewers for carefully reading our manuscript and for giving detailed comments and suggestions that have been helpful to improve the manuscript. %---------------------------------------------------------------------------- \begin{thebibliography}{} \bibitem{AKSS} M. Ajtai, J. Koml\'os, M. Simonovits, and E. Szemer\'edi. \newblock Proof of the Erd\H{o}s-T. S\'os conjecture for large trees. Unpublished. \bibitem{AY} N. Alon and R. Yuster. \newblock The Tur\'an number of sparse spanning graphs. \newblock {\em J. Comb. Theory Ser. B}, 103(3):337--343, 2013. \bibitem{BD} S. Balasubramanian and E. Dobson. \newblock Constructing trees in graphs with no $K_{2,s}$. \newblock{\em J. Graph Theory}, 56:301--310, 2007. \bibitem{BP} J. Balogh and C. Palmer. \newblock On the Tree Packing Conjecture. \newblock{\em SIAM J. Discrete Math.}, 27(4):1995--2006, 2013. %\bibitem{Bol} %B. Bollob\'as, Some remarks on packing trees, Discrete Math. 46 (1983) 203--204. %\bibitem{BE} %B. Bollob\'as, S.E. Eldridge, Packing of graphs and applications to %computational complexity, J. Combin. Theory Ser. B 25 (1978) %105--124. \bibitem{HBK} B.A. Bourgeois, A.M. Hobbs, and J. Kasiraj. \newblock Packing trees in complete graphs. \newblock{\em Discrete Math.}, 67:27--42, 1987. %\bibitem{BHPT} %J. B\"ottcher, J. Hladk\'y, D. Piguet, and A. Taraz, An approximate version of the tree %packing conjecture. \bibitem{Dob} E. Dobson. \newblock Constructing trees in graphs whose complement has no $K_{2,s}$. \newblock{\em Combin. Probab. Comput.}, 11:343--347, 2002. \bibitem{ET} N. Eaton and G. Tiner. \newblock On the Erd\H{o}s-S\'os conjecture for graphs having no path with $k+4$ vertices. \newblock{\em Discrete Math.}, 313:1621--1629, 2013. %\bibitem{Fan1} %G. Fan, The Erd\H{o}s-S\'os conjecture for spiders of large size, Discrete %Math. 313 (2013) 2513--2517. \bibitem{FS} G. Fan and L. Sun. \newblock The Erd\H{o}s-S\'os conjecture for spiders. \newblock{\em Discrete Math.}, 307:3055--3062, 2007. \bibitem{Bol2} R.L. Graham, M. Gr\"otschel, and L. Lov\'asz, Eds. \newblock{\em Handbook of combinatorics.} Vol. 1,2. Elsevier Science B.V., Amsterdam, 1995. \bibitem{Gya} A. Gy\'arf\'as and J. Lehel. \newblock Packing trees of different order into $K_n$. \newblock In {\em Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Colloq. Math. Soc. J\'anos Bolyai}, volume 18 pages 463--469, North-Holland, Amsterdam, 1978. \bibitem{JLR} S. Janson, T. \L uczak, and A. Ruci\'nski. \newblock Random graphs. \newblock{\em Wiley-Interscience Series in Discrete Mathematics and Optimization}, Wiley-Interscience, New York, 2000. %\bibitem{KSS} %J. Koml\'os, G.N. S\'ark\"{o}zy and E. Szemer\'edi, Spanning trees in dense graphs, %Combin. Probab. Comput. 10, 5 (2001), 397--416. \bibitem{ML} A. McLennan. \newblock The Erd\H{o}s-S\'os conjecture for trees of diameter four. \newblock{\em J.Graph Theory}, 49(4):291--301, 2005. %\bibitem{Rod} %Y. Roditty, Packing and covering of the complete graph. III. On the tree packing conjecture, %Sci. Ser. A Math. Sci. (N.S.) 1 %(1988) 81--85. %\bibitem{SS} %N. Sauer, J. Spencer, Edge disjoint placement of graphs, J. Combin. %Theory Ser. B 25 (1978) 295--302. \bibitem{Sid} A.F. Sidorenko. \newblock Asymptotic solution for a new class of forbidden graphs. \newblock{\em Combinatorica}, 9(2):207--215, 1989. \bibitem{STY} P. Slater, S. Teo, and H. Yap. \newblock Packing a Tree with a Graph of the Same Size. \newblock{\em J. Graph Theory}, 9:213--216, 1985. \bibitem{Tin} G. Tiner. \newblock On the Erd\H{o}s-S\'os Conjecture for Graphs on $n=k+3$ Vertices. \newblock{\em Ars Combin.}, 95:143--150, 2010. \bibitem{W} J.F. Sacl\'e, M. Wo\'zniak. \newblock The Erd\H{o}s-S\'os Conjecture for graphs without $C_4$. \newblock{\em J. Combin. Theory Ser. B}, 50:367--372, 1997. \bibitem{W2} M. Wo\'zniak. \newblock On the Erd\H{o}s-S\'os Conjecture. \newblock{\em J. Graph Theory}, 21:229--234, 1996. %\bibitem{ZL} %S. Zaks and C.L. Liu, %Decomposition of graphs into trees, In %Proceedings of the Eighth %Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana %State Univ., Baton Rouge, La., 1977) %(Winnipeg, Man., 1977), Utilitas Math., pp. 643-- %654. Congressus Numerantium, No. XIX. \bibitem{Zhou} B. Zhou. \newblock A note on the Erd\H{o}s-S\'os Conjecture. \newblock{\em Acta Math. Sci.}, 4:287--289, 1984. \end{thebibliography} \end{document}