What is the probability that a random simple graph on [n] is a tree?

Question

What is the probability that a random simple graph on [n] is a tree?

Just started probability in combinatorics class, not sure how to tackle this.

Answer 1

If you're talking about uniformly chosen random graph (same as Erdos-Renyi with $p=1/2$), then there are $n^{n-2}$ labeled trees on $n$ vertices by Cayley's formula (see https://en.wikipedia.org/wiki/Cayley%27s_formula ). The probability of any one of these coming up is $2^{-n(n-1)/2}$, so it's $$ 2^{-n(n-1)/2} n^{n-2} $$ If you dispose of the "labeled" condition, but are still choosing uniformly, this is the sort of situation where there is almost surely no closed/explicit/useful formula. However, there are $2^{\binom{n}{2}}/n! (1+o(1)) = 2^{n(n-1)/2}e^{n}n^{-n-1/2}(\sqrt{2 \pi}+o(1))$ graphs (almost all graphs have no nontrivial automorphism + Stirling) and there are $C \alpha^n n^{-5/2} (1+o(1))$ trees on $n$ vertices (Otter 1948), where $\alpha = 2.955765\ldots$ and $C = 0.5349496\ldots$. Therefore, the probability you seek is $$ 2^{-n^2/2} \beta^n n^{n-2} (C'+o(1)) $$ where $\beta = \sqrt{2} \alpha/e \approx 1.5377667\ldots$ and $C' = C \sqrt{2 \pi} \approx 1.3409198\ldots$.