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.

  • $\begingroup$ What is $M(\ldots)$ in $(5.2)$? $\endgroup$ – Hagen von Eitzen Mar 14 at 5:13
  • $\begingroup$ @HagenvonEitzen I guess that's the expected value and $D^2$ is the variance. $\endgroup$ – leon Mar 14 at 12:06
  • $\begingroup$ 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. $\endgroup$ – Chris Godsil Mar 14 at 12:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.