Probability that an undirected graph has cycles If we know the probability $P$ that there exists an edge between two vertices of an undirected graph, let's say $P= 1/v$,  where $v$ is the number of vertices in the graph, what is the probability that the graph has cycles?
I've twisted my brain with this. Can anyone help?
 A: If a closed form for this probability were known for general $p$, we could substitute $p=1/2$ into it to get $2^{-v(v-1)/2}$ times the number of forests on $v$ labeled vertices. This is OEIS sequence A001858. That page gives an exponential generating function and a recurrence relation for this sequence, but no closed form, so presumably no closed form is known. It seems unlikely that the special case $p=1/v$ is easier to solve, so I would expect that you won't find a closed form for this.
The number $T(v,k)$ of forests on $v$ labeled vertices with $k$ edges is given by OEIS sequence A138464. That page gives recurrence relations. You can use these numbers to find the desired probability as
$$
\sum_{k=0}^{v-1}p^k(1-p)^{v(v-1)/2-k}T(v,k)\;.
$$
A: If the graph is known to be connected: The  graph has no cycles iff it is a tree.  
By Cayley's formula, the number of trees that can be formed with $v$ vertices is $v^{v-2}$
A tree with $v$ vertices has $v-1$ edges. The probability that a specific tree can be formed is 
$P^{v-1}\cdot(1-P)^{k-v+1}$
where 
$k=v\cdot(v-1)/2$, 
adding up to  
$v^{v-2}\cdot P^{v-1}\cdot(1-P)^{k-v+1}$. 
The case that the graph can be disconnected is complicated. It takes the distinct combinations of disconnected  graphs. I havn't seen a study on this and don't have one mine here. 
EDIT: joriki's solution seems to be covering it for the general case.
