Hello, given graph $G=(V,E)$ with $n=|V|$ and $k=|E|$, what is the probability that it does not contain any cycle $C\_l$ for $l\geq3?$


**The requested clarification**:
My intention was to form the question in such a way, that there is no information about any distribution of the edges, and *n* and *k* are parameters. This lack of information should be in fact the information. You construct graphs in any possible ways, and you have to decide which constructs are more possible to occur and which are less expected. This probably implies the uniform distribution.



Probability, that a graph G does not contain a cycle
I will assume the uniform distribution on all (labelled) graphs with $n$ vertices and $k$ edges. An acyclic graph on $n$ vertices has at most $n-1$ edges, so let me further assume $k< n$. More precisely, $k=n-c$, where $c$ is the number of connected components, i.e., the graph is acyclic iff it is union of $c$ disjoint trees. Now, the number of trees with $m$ vertices is $m^{m-2}$ by [Cayley’s formula](http://en.wikipedia.org/wiki/Cayley%27s_formula), hence the requested probability is


$$p\_{n,k}=\frac1{(n-k)!\binom{\binom n2}k}\sum\_{\substack{n\_1+\cdots+n\_{n-k}=n\\n\_1,\dots,n\_{n-k}>0}}\binom n{n\_1\,\dots\,n\_{n-k}}\prod\_{i=1}^{n-k}n\_i^{n\_i-2}.$$


We have $\binom{\binom n2}k\approx\left(\frac{en^2}{2k}\right)^kk^{-1/2}$ by Stirling’s approximation (where $f\approx g$ means $c\_1f\le g\le c\_2f$ for some positive constants $c\_1,c\_2$), hence in the simplest case $k=n-1$,


$$p\_{n,n-1}\approx\frac1{\sqrt n}\left(\frac2e\right)^n.$$


