6
$\begingroup$

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?

  • 0
    Presumably the existences of different edges are independent?2012-12-18

2 Answers 2

4

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

1

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.

  • 0
    You're right, I misread. I've removed my downvote.2012-12-18