Consider a graph with vertices 1,...,n and suppose that each of the $\binom{n}{2}$pairs of vertices is, independently, an edge of this graph with probability p.Let $P_n$ denote the probability that this graph is connected.

(a)I want to derive an expression that involves $P_k$ for the probability that the vertex set {1,...,k} is a component of this graph.

(b) I want to derive the probability that vertex 1 is a member of a component of size k.

(c)I want to express $P_n$ in terms of $P_k$, k=1,...,n-1.

(d)Using the recursion of part (c) to find $P_6$


I know the probability that random graph is connected $\sim$ $\sqrt{\frac{\pi}{2n}}$ for large n

I also know the expected value of the number of components in the random graph

$E[C]=\displaystyle\sum_{k=1}^n \binom{n}{k}\frac{(k-1)!}{n^k}$

How to use this corollary and equation of the number of components in the random graph to answer this question? Your hints are needed.

  • $\begingroup$ In (a), what do you mean by "is a component of this graph"? $\endgroup$ – usul May 23 '16 at 14:47
  • $\begingroup$ A graph is said to consist of r components if its vertices can be partitioned into r subsets so that each subset is connected and, in addition, there are no edges between vertices in different subsets. $\endgroup$ – Dhamnekar Winod May 23 '16 at 14:57
  • $\begingroup$ That doesn't directly answer my question, but I guess you want that $\{1,\dots,k\}$ is a connected component and is disconnected from the rest of the graph. OK, this is just $P_k$ times the probability that none of the vertices $\{k+1,\dots,n\}$ are connected to any of the vertices $\{1,\dots,k\}$ because the edges are independent. $\endgroup$ – usul May 23 '16 at 15:54
  • $\begingroup$ I want expression for $P_n$ which involves $P_k$ indicating the probability that the vertex set {1,...,k} is the component of this graph $\endgroup$ – Dhamnekar Winod Sep 14 '16 at 14:51

Your Answer

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

Browse other questions tagged or ask your own question.