\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)|<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}
\prf 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.\]\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)|<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}
\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}}
<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}{}
\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}
