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?
On
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.
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)\;. $$