A tree $T$ is given. Starting with the complete graph on $n$ vertices, subgraphs isomorphic to $T$ are erased at random until no such subgraph remains. For what trees does there exist a positive constant $c$ such that the expected number of edges remaining is at least $cn^2$ for all positive integers $n$?
David Yang.
Such tree does not exist.
First two useful assertions.
Fact 1. Every graph $G$ has a subgraph $H$ with $\delta(H) > \frac{|E(G)|}{|V(G)|}$.
Here $\delta(H) = \min_{v\in V(H)} \deg(v)$.
Fact 2.. If $T$ is a tree and $G$ is any graph with $\delta(G) \geq |T|-1$ then $G$ has a subgraph isomorphic to $T$.
Both propositions can be found in R.Diestel's "Graph Theory".
Now assume that there exists a given graph $T$ with required property. Let take big enough $n$ such that $c n > |T|$. Then after a process of erasing of complete graph with $n$ vertices we get a graph $G$ with more than $c n^2$ edges, who does not contain a subgraph isomorphic to $T$.
Certainly $\frac{|E(G)|}{|V(G)|} \geq c n$. Using fact 1, there is a subgraph $H$ of $G$ with $\delta(H) > c n > |T| -1$. Using fact 2 we will obtain a subgraph of $H$ (and also of $G$) isomorphic to $T$, contradiction.