\documentclass[12pt]{article} \usepackage{e-jc} \specs{P1.52}{23(1)}{2016} \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{\begin{prf}}{\noindent{\it Proof.} } \newcommand {\cbdo}{\hfill$\Box$} %\newcommand{\mod}{\ \def\mod{\mathop{\rm mod}\nolimits} \date{\dateline{Jul 13, 2015}{Mar 3, 2016}{Mar 18, 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} Ajtai, Koml\'os, Simonovits and Szemer\'edi have announced a proof of Conjecture \ref{cjES} for sufficiently large k. There are 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} \begin{proof} 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.\end{proof} 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} \begin{proof} 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).\qedhere\]\end{proof} 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} \begin{proof} 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 $$ Pr\left[|D_i|\leq \frac{p|A_i|}{2e}\right]\leq {\rm exp}\left( -\frac{p|A_i|}{8e}\right).\qedhere $$ \end{proof} \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.\qedhere\]\end{proof} 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} \begin{proof} 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.\end{proof} 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} \begin{proof} 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. \end{proof} 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} \begin{proof} 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.\qedhere\] \end{proof} 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} \begin{proof} 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. \end{proof} 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}{99} \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}