Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Presumably the existences of different edges are independent? –  joriki Dec 18 '12 at 22:12
add comment

2 Answers 2

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

share|improve this answer
add comment

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.

share|improve this answer
    
@Micah If you read more closely, the answer covers if.. . yours on the other hand seems to be a quick conclusion. –  ashley Dec 18 '12 at 22:46
    
You're right, I misread. I've removed my downvote. –  Micah Dec 18 '12 at 22:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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