# Almost all graphs have a subgraph from a large class of graphs with constant order

I will pose the question in relation to trees but the more general question that can be deduced from the title of this post is also very interesting.

I suspect the question might have a very trivial answer using some of the relatively modern tools of which I am unaware.

Denote by $T_k$ the set of all trees on $k$ vertices (up to isomorphism). Let $c$ be a positive integer and let $T$ be a subset of $T_c$ such that $$|T| > \frac{|T_c|}{2}$$

For $n \geq c$ let $p_n$ be the probability that a tree, chosen uniformly at random from $T_n$ contains as a subgraph at least one tree from $T.$

Is the following statement true or false?

$p_n \rightarrow 1$ as $n \rightarrow > \infty \; \; (1)$ ?

It seems to me that the following does not hold if we consider labeled trees, but I am not sure how to smartly compute the ratio $\frac{T_n'}{T_n}$ where $T_n'$ is the subset of all trees from $T_n$ such that every graph in $T_n'$ has some subgraph from $T.$

Is the above statement true? Is there any way to relax the inequality? If not, is there a way to (non trivially) restrict the inequality so that $(1)$ holds?

-

Let $T$ be any tree of size $c$, and let $p_n(T)$ be the probability that a uniformly chosen tree $T_n$ of size $n$ contains a copy of $T$. I claim that $p_n(T)\to1$ as $n\to\infty$ (which implies what you want).

A tree can be coded by its contour function (or Dick path); a random tree of size $n$ (say, of $n$ edges) corresponds to a random walk excursion conditioned to come back to $0$ after $2n$. Now, look at the contour function of $c$: we want to know whether this occurs somewhere along that of $T_n$ (this will imply that $T_n$ contains a copy of $T$). But given the first $m$ steps of $T_n$ (for $m \leq n/2-2c$), this occurs on the interval $[m,m+2c]$ with probability of order $e^{-\lambda c}$, so it will occur /somewhere/ with probability going to $1$ as long as $c$ is fixed.

Maybe there is some bookkeeping to be done, e.g. maybe this is only for binary trees or something; and certainly the lower bound on $p_n$ is very bad. But it seems to at least partially answer the question.

-
We can ask not only that something appears as a subtree, but that it appears as a "limb". A limb of a tree $T$ at a vertex $v$ is a maximal subtree of $T$ that includes $v$ and a neighbouring vertex. (Informally, separate $T$ at $v$ with each fragment getting its own copy of $v$; these fragments are the limbs.) Schwenk proved in 1971 that the number of (unlabeled) trees of order $n$ containing a given limb depends only on the size of the limb and not on its structure. From this he proved that almost all trees contain any given subtree as a limb. This is quite a bit stronger than what you request.