# Almost all trees have non-trivial automorphism group

In their paper Asymmetric Graphs Erdős and Rényi proved that almost all trees have non-trivial automorphism group. More specifically they showed that almost all trees contain at least one so-called cherry, i.e. three vertices $$i, j, k$$ where $$i, j$$ are leaves, $$k$$ has degree $$3$$ and $$(i,k)$$ and $$(j,k)$$ are edges.

Unfortunately I'm having some trouble understanding their proof. I can follow the counting argument but fail to understand the following bits, in particular the part where Chebyshev's inequality is used. I would be very grateful if someone could explain to me the steps in the proof in more detail or point me to some other reference for this result. I haven't found this in any graph theory book.

I have linked the original paper above. The relevant bit starts on page 18 of the pdf.

• What is $M(\ldots)$ in $(5.2)$? – Hagen von Eitzen Mar 14 at 5:13
• @HagenvonEitzen I guess that's the expected value and $D^2$ is the variance. – leon Mar 14 at 12:06
• Mcavaney cambridge.org/core/journals/… has a short proof that almost all trees contain a given limb; tis immediately implies the result of Erdős and Rényi. – Chris Godsil Mar 14 at 12:13