\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)|<tn/2$, we have 
\begin{align}\label{delta}
\delta(G)\leq t-1
\end{align}
Suppose first that there is a vertex $v\in V(G)$ with $d_G(v)\geq t+\frac{k-1}{2}$. Clearly, 
\[|E(G-v)|= |E(G)|-d_G(v)< \frac{t(k+t)}{2}-t-\frac{k-1}{2} =\frac{(t-1)(k+t-1)}{2}.\] 
Thus, by the induction hypothesis, $G-v$ and $T$ pack. Therefore, 
$G$ and $T$ pack as well. 

Hence, we may assume that 
\begin{align}\label{Delta}
\Delta(G) \leq t-1+\frac{k}{2}
\end{align}
Let $S_i\subset V(G)\setminus N[v_i]$ 
with the assumption that if $u\in S_i$ then $d_G(u)< 5c$. 


\begin{cl}\label{sinowe}
$|S_i|\geq \frac{n}{4}+t$
\end{cl}
\begin{proof} By (\ref{Delta}) each vertex of $G$ has 
at least 
\[k+t-1-(t-1+k/2)=k/2\] 
non-neighbors. Suppose that $\alpha$ vertices of $G$ have degree 
greater than or equal to $5c$. Thus
\[ cn>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)|<cn/2$, by Proposition \ref{ity} 
\begin{align}\label{ix}
z\leq  c {n}^{3/4}.
\end{align}
This stage is done repeatedly for $i=1,\dots, z$ and throughout it we maintain the following invariants:
\begin{enumerate}
\item
At iteration $i$ we match $v_i$ (if it is not matched in Stage 1) with some vertex $f(v_i)$ of $G'$ 
such that $f(v_i)\in P'\cup I'$. 
\item Furthermore,  
we also make sure that all neighbors of $f(v_i)$ in $G'$ are matched to vertices of $S_i\cup \{v_n\}$. 
\end{enumerate}
Note that because $G'$ is acyclic and since there are no edges 
(in $G$) between $v_i$ and $S_i\cup \{v_n\}$ for those $v_i$ that 
are non-neighbors of $v_n$, such a mapping does 
not violate the packing property.  

To see that this mapping is possible, consider the $i$'th 
iteration of Stage 2, where $v_i$ is a vertex of 
$G$ with $d_G(v_i)\geq {n}^{1/4}\geq 5c$. In particular 
$v_i \not\in \bigcup_{j=1}^{i-1}S_j$. Thus, if $v_i$ is already 
matched, then it was matched in Stage 1 and so $f(v_i)\in I'$. 
Then, the second invariant of Stage 2 is automatically preserved 
because $f(v_i)$ is isolated.
 
Therefore, we may assume that $v_i$ is yet unmatched. 
In this case we may take $f(v_i)$ to be any vertex of $P'$. 
Indeed, note that $|P'|\geq z$ 
and before iteration $i$, the number of 
already matched vertices of $P'$ was at most $i-1$.
  
Furthermore, observe that since $v'_1$ is a common neighbor 
of all $f(v_j)$, $j=1,\dots,i$,  
at iteration $i$ the overall number of matched vertices is at most 
\begin{align}\label{wzor1}
 \delta(G)+1+iq\leq t+zq\leq t+n/59.
 \end{align}
Let $R'$ be the set of neighbors of $f(v_i)$ in $G'$ that are still unmatched. 
Note that $R'$ contains all neighbors of $f(v_i)$ apart from $v'_1$. 
Thus, in order to maintain the second invariant, 
it suffices to match vertices of 
$R'$ with some vertices of $S_i$. 
Note that by the choice of $P'$ and since $v'_1$ is already 
matched, $|R'|\leq q-1$. 
Let $Q$ be the set of yet unmatched vertices of $S_i$.   
By Claim \ref{sinowe} and formula (\ref{wzor1}), 
\[|Q|\geq n/4+t-(t+n/59)\geq \frac{{n}^{1/4}}{59c}> 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}}
<n/4
\end{align}
Therefore, by (\ref{ku}),  
$|Q\setminus Y| >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}/180<n/4
\end{align}
Let $W'=\{w'_1,\dots,w'_y\}\cup\{v'_1\}$. 
By (\ref{stopienwh'}), 
\begin{align}\label{deltawu'}
\Delta(G'-W')\leq \Delta(H'-W')+1\leq 360\sqrt{n}+1.
\end{align}
Furthermore, $|V(G')\setminus M'_3|\geq n-n/4=3n/4$. Thus $G'-M'_3$ has an independent set $J'$ with $|J'|\geq 3n/8$. 
Let $K'=V(G')\setminus (J'\cup M'_3)$. 

In Stage 4 we match vertices from $K'$ one by one, with arbitrary  yet unmatched vertices of $G$. 
Suppose that $v'\in K'$ is still unmatched. 
Let $Q$ be the set of all yet unmatched vertices of $G$. Clearly, $|Q|\geq |J'|\geq 3n/8$ 
since the vertices of $J'$ remain unmatched in every step of Stage 4. 
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$. 
By (\ref{deltawu'}), $|X'|\leq 360\sqrt{n}+1$. 
Furthermore, by the second invariant of Stage 2, 
\[X' \subseteq V(G')\setminus \{f(v_1),\dots,f(v_z)\}\]
and so 
\[f^{-1}(X') \subseteq V(G)\setminus W.\]
Hence, by (\ref{deltawu}), 
\[|Y|\leq |X'|\cdot n^{1/4}<3n/8.\]
Hence
\[|Q\setminus Y|>0,\] 
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}
