Probability, that a graph G does not contain a cycle

Question

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.

Answer 1

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, 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.$$

Answer 2

I will assume what seems the more natural question: uniform probability over all labeled graphs with exactly $k$ edges and $n$ vertices (rather than on isomorphism classes of graphs). The number of labeled forests with $k$ edges on $n$ vertices is the integer sequence http://oeis.org/A138464 which doesn't seem to indicate that a closed form expression is known. To obtain the probability divide this number by (($n$ choose 2) choose $k$).