This one is exercise 13, chapter 7 from Reinhard Diestel's Graph theory (Third edition). First of all, we prove the following result (proposition 1.2.2 in the book): Every graph $G$ contains a subgraph $H$ such that $\delta(H)\geq \varepsilon(H)\geq\varepsilon(G)$, where $\delta(G)$ is the minimum degree of $G$ and $\varepsilon(G)=|E(G)|/|V(G)|$. Proof: We make the following sequence: $G_0:=G, G_1,..., G_i$ so that $G_k$ is a graph obtained from $G_{k-1}$ by deleting a vertex of degree at most $\varepsilon(G_k)$. We end the sequence when there is no vertex left. The sequence obviously ends (in the worst case with the void graph), but actually $G_i$ is non-void, because it is easy to prove that $\varepsilon(G_k)\geq \varepsilon(G_{k-1})$ (just use the definition). As $\varepsilon(G)>0$ (the other case is trivial...) we get that $G_i$ is non-void. Because the sequnce ended at $G_i$, there is no vertex left to remove, so $\delta(G_i)>\varepsilon(G_i)$ so we may choose $H:=G_i$. $\square$ Choose now $c=|T|-1$. Take a subgraph $H$ as in the lemma. For the graph $T$, we put one of its vertices as the root, the vertex of rank 0, its direct neighbours the vertices of rank 1, their neighbours not already taken as the vertices of rank 2 and so on. We now construct the subgraph inductively: take a vertex as the root. So now suppose that we have constructed the vertices of rank $i$, and we want to construct those of rank $i+1$. Let the constructed graph be $T_i$. Take one of the vertices $v$ of rank $i$. Say that it has $a$ neighbours of rank $i+1$ in $T$. Let $b$ be the number of vertices of $T_i$. Then $a+b\leq |T|$ so our vertex has at least $a$ neighbours in $H$ not already in $T_i$. Add these vertices to $T_i$, and add only the edges that connect these vertices to $v$. We now continue with our new graph $T_i$, take another vertex of degree $i$ and so on, till we obtain the graph $T_{i+1}$. Continuing in the same manner we get our subgraph isomorphic to $T$.

Let the tree $T$ have vertices $\{t_1,\ldots,t_r\}$ with degrees $d_1,\ldots,d_r$. We write $t_i\sim t_j$ if the two are adjacent in $T$. Now, let $G=(V,E)$ be a graph with $n$ vertices and $m$ edges. We define a $T$-labeling of $G$ to be a function \[f:[r]\to V\]where $f(i)\sim f(j)$ (adjacency in $G$) if $t_i\sim t_j$. Note that if we have a $T$-labeling $f$ of $G$ that is injective, then the problem is solved. Our approach will be to pick the $T$-labeling of $G$ randomly and showing that there is a non-zero probability that it is injective. Pick a specific $T$-labeling $f$ with probability \[\frac{1}{2m}\prod_{i=1}^r\left(\frac{1}{\mathrm{deg}(f(i))}\right)^{d_i-1}.\]It isn't clear that the sum of this over all $T$-labelings is $1$, but that fact will be a corollary of the following lemma. Lemma: Root the tree $T$ at $t_i$, and label its vertices by distance to the root. Now, select $T$-labelings randomly in the following manner. Pick $f(i)$ randomly with probability $\mathrm{deg}(v)/2m$ of picking $v\in V$. Now, if $t_k$ is a descendant of $t_j$ and if $f(j)$ is chosen, choose $f(k)$ randomly from $N(f(j))$, the neighbors of $f(j)$ uniformly at random. This way, we randomly pick a $T$-labeling. Then, the random distribution on $T$-labelings from this procedure is identical to that given above. Proof: Suppose that using the given process, we end up with some $T$-labeling $f$. The probability we got this particular $f$ is \[\frac{\mathrm{deg}(f(i))}{2m}\cdot\left(\frac{1}{\mathrm{deg}(f(i))}\right)^{d_i}\prod_{\substack{j=1\\ j\ne i}}^r\left(\frac{1}{\mathrm{deg}(f(j))}\right)^{d_j-1},\]since the probability we pick the correct descendants of $t_j$ is $\left(\frac{1}{\mathrm{deg}(f(j))}\right)^{d_j-1}$ since $t_j$ has exactly $d_j-1$ descendants. This formula matches the one given before the lemma, so the lemma is proven. $\blacksquare$ Using this lemma, we have the following claim. Claim: Fix two vertices $t_i$ and $t_j$ of $T$. Then, $\mathrm{Pr}[f(i)=f(j)]\le \frac{n}{2m}$ if we pick $f$ randomly in the way described above. Proof: Root the tree $T$ at vertex $t_i$. The lemma then makes it clear that if we fix $f(i)$, the probability distribution for $f(j)$ was as if $T$ was simply a path from $t_i$ to $t_j$ of length equal to the distance between $t_i$ and $t_j$ in $T$. Thus, for the purposes of this lemma, we may assume that $T$ is indeed a path from $t_i$ to $t_j$. To make notation simpler, we will assume that $T$ is the path $(t_1,\ldots,t_r)$, and we'll show that $p:=\mathrm{Pr}[f(1)=f(r)]\le\frac{n}{2m}$. We see that $p$ is given by summing over all walks $v_1\sim v_2\sim\cdots\sim v_r$ of \[\frac{1}{2m}\frac{1}{\mathrm{deg}(v_2)}\cdots\frac{1}{\mathrm{deg}(v_{r-1})}\mathbf{1}_{v_1=v_r}.\]This is equivalent to the sum over all walks $v_2\sim\cdots\sim v_{r-1}$ of \[\frac{1}{2m}\frac{1}{\mathrm{deg}(v_2)}\cdots\frac{1}{\mathrm{deg}(v_{r-1})}|N(v_2)\cap N(v_{r-1})|.\]We see that $|N(v_2)\cap N(v_{r-1})|\le|N(v_{r-1})|=\mathrm{deg}(v_{r-1})$, so \[p\le\frac{1}{2m}\sum_{v_2\sim\cdots\sim v_{r-1}}\frac{1}{\mathrm{deg}(v_2)}\cdots\frac{1}{\mathrm{deg}(v_{r-2})}.\]But \begin{align*} \sum_{v_2\sim\cdots\sim v_{r-1}}\frac{1}{\mathrm{deg}(v_2)}\cdots\frac{1}{\mathrm{deg}(v_{r-2})}&=\sum_{v_2\sim\cdots\sim v_{r-2}}\sum_{v_{r-1}\sim v_{r-2}}\frac{1}{\mathrm{deg}(v_2)}\cdots\frac{1}{\mathrm{deg}(v_{r-2})}\\ &=\sum_{v_2\sim\cdots\sim v_{r-2}}\frac{1}{\mathrm{deg}(v_2)}\cdots\frac{1}{\mathrm{deg}(v_{r-3})}, \end{align*}and inductively applying this process shows that \[p\le\frac{1}{2m}\sum_{v_2\in V}1=\frac{n}{2m},\]as desired. $\blacksquare$ Now, we see that the probability that $f$ is not injective is at most \[\sum_{1\le i<j\le r}\mathrm{Pr}[f(i)=f(j)]\le\binom{r}{2}\frac{n}{2m}=\frac{1}{2}\binom{r}{2}\frac{1}{c},\]by the union bound. Thus, if we pick $c>\frac{1}{2}\binom{r}{2}$, then the probability that $f$ is injective is less than $1$, so there is some $T$-labeling $f$ that is injective, as desired.

I think, David Yang had been studying R.Diestel's book at that moment. Because the problem follows by two claims there: Proposition 1.2.2 and Corollary 1.5.4. The first one guarantees existence of a subgraph with large minimal degree if the graph has enough edges. The latter guarantees existence of a subgraph isomorphic to a given tree if all degrees of the graph are greater than the number of edges of the tree.

ELMO Shortlist 2011 C7 wrote: Let $T$ be a tree. Prove that there is a constant $c>0$ (independent of $n$) such that every graph with $n$ vertices that does not contain a subgraph isomorphic to $T$ has at most $cn$ edges. David Yang. Let us suppose the tree $T$ has $t$ vertices. We prove the below general lemmas. Lemma 1: In a graph $G$ with$V$ vertices and $E$ edges there exists an induced subgraph $H$ with each vertex having degree atleast $\frac{E}{V}$. Proof : We call a vertex unwanted if it has degree less than $\frac{E}{V}$. From graph $G$ we start deleting unwanted vertices. But in this process some normal vertices might become unwanted. Notice that the the ratio of edges to vertices is continuously increasing. Hence it is impossible for only one vertex to remain at the end of this process. Therefore we can conclude that this process terminates and we are left with a graph in which there is no unwanted vertices. Lemma 2 : Given a graph $G$ in which each vertex has degree at least $n-1$ and a tree $T$ with $n$ vertices, there is a subgraph of $G$ isomorphic to $T$. Proof : This can be proven by simple induction. Claim : Let $T$ be a tree with $t$ vertices,and let $G$ be a graph with $n$ vertices. If $G$ has atleast $n(t-1)$ edges, then $G$ has a subgraph isomorphic to $T$. Proof : By lemma $1$ , $G$ has a subgraph $H$ such that all the vertices in $H$ have a degree atleast $t-1$. Then we apply lemma $2$ on $H$ to obtain the fact that $H$ has a subgraph isomorphic to a tree $T$ with $t$ vertices. Now setting $c = t-1$ and using the claim , we reach the desired conclusion.