Intereting Posts

Is the number $-1$ prime?
$\sqrt{2}\notin\mathbb{Q}$ but …
How to reverse digits of an integer mathematically?
How to find all the coset leaders? (follow-up to a previous question)
To evaluate integral using Beta function – Which substitution should i use?
Evaluate the series $\sum_{n = 0}^\infty \frac{1}{(2n + 1)^6}$ by examining the real Fourier series of the function $f(x) := x(\pi – |x|)$
Evaluate $ 1 + \frac{1}{3}\frac{1}{4}+\frac{1}{5}\frac{1}{4^2}+\frac{1}{7}\frac{1}{4^3}+\dots$
Prove that $ f(x) $ has at least two real roots in $ (0,\pi) $
Maximal order of an element in a symmetric group
Coupon collector's problem using inclusion-exclusion
$\int_X f^p d\mu = p\int_{[0,+\infty)} t^{p-1}\mu(\{x\in X: f(x)>t\}) d\mu_t$ for any natural $p\ge 1$
On critical points of a large function
Spectral Measures: Spectral Spaces (II)
A sum of fractional parts.
Limits along what curves suffice to guarantee the existence of a limit?

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?

- Is the empty graph connected?
- Prove that a connected graph not having $P_4$ or $C_3$ as an induced subgraph is complete bipartite
- Why can't reachability be expressed in first order logic?
- Reduction from Hamiltonian cycle to Hamiltonian path
- How many edges does an undirected tree with $n$ nodes have?
- What condition need to be imposed on Havel-Hakimi theorem to check for connected graph?

- Bipartite graph with larger average on one side
- Minimal cut edges number in connected Eulerian graph.
- to clear doubt about basic definition in graph theory
- Understanding the Proof of Dirac's Theorem Regarding Graph Connectivity
- How to draw that graph?
- Rank of an interesting matrix
- Checking whether a graph is planar
- Proof on minimal spanning tree
- eigen decomposition of an interesting matrix (general case)
- Show that a graph with 9 vertices has at least five vertices of degree 6, or at least six vertices of degree 5.

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

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.

- When is a metric space Euclidean, without referring to $\mathbb R^n$?
- The product of a subgroup and a normal subgroup is a subgroup
- asymptotic expansion from 3 leading terms
- Quotient ring of Gaussian integers
- Why is the Cauchy product of two convergent (but not absolutely) series either convergent or indeterminate (but does not converge to infinity)?
- why is the following thing a projection operator?
- How do you find the Maximal interval of existence of a differential equation?
- Reference for multivariable calculus
- Is $p(p + 1)$ always a friendly number for $p$ a prime number?
- Distribute n identical objects into r distinct groups
- If $(a,b)=1$ then prove $(a+b, ab)=1$.
- It seems like a nim variant
- Solving $x^4-y^4=z^2$
- Why does $\sum a_i \exp(b_i)$ always have root?
- Suppose $f: \Rightarrow \mathbb{R}$ is continuous and $\int_0^x f(x)dx = \int_x^1 f(x)dx$. Prove that $f(x) = 0$ for all $x$