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?

  • $\begingroup$ Presumably the existences of different edges are independent? $\endgroup$ – 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




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.

  • $\begingroup$ @Micah If you read more closely, the answer covers if.. . yours on the other hand seems to be a quick conclusion. $\endgroup$ – ashley Dec 18 '12 at 22:46
  • $\begingroup$ You're right, I misread. I've removed my downvote. $\endgroup$ – Micah Dec 18 '12 at 22:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.