# 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?

-
Presumably the existences of different edges are independent? – joriki Dec 18 '12 at 22:12

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

-

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

$v^{v-2}\cdot P^{v-1}\cdot(1-P)^{k-v+1}$.