# probability that the vertex set {1,…,k} is component of random graph

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
$E[C]=\displaystyle\sum_{k=1}^n \binom{n}{k}\frac{(k-1)!}{n^k}$
• 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. – usul May 23 '16 at 15:54
• 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 – Dhamnekar Winod Sep 14 '16 at 14:51