Suppose we have a random undirected graph G(4, 1/2), i.e. the probability of any two of the four total vertices being connected is 1/2.
how to find the probability that Probability (G(4, 1/2) is connected)=?
Can someone give me idea how to do it.
Thanks alot!
Any graph with at most $2$ edges is disconnected, any graph with at least $4$ edges is connected (since there are only $3$ edges among any $3$ of the vertices). Thus you can do most of the work by summing probabilities for numbers of edges without dealing with specific configurations. Then you just have to consider which configurations of $3$ edges make the graph connected and count them.
More explicit solution in response to the comments:
The probability that there are $k$ edges is $P(K=k)=2^{-6}\binom6k$. You can either add these probabilities for $k$ from $4$ to $6$, or use the symmetry $P(K\lt3)=P(K\gt3)$ to get
$$ P(K\gt3)=\frac{1-P(K=3)}2=\frac{1-\frac{20}{64}}2=\frac{11}{32}\;. $$
To this you need to add the probability of getting a connected graph with $3$ edges. You correctly counted $16$ connected cases ($\binom63=20$ cases minus the $4$ in which all $3$ edges are among $3$ vertices), so this probability is $\frac{16}{64}$, for a total of
$$ \frac{11}{32}+\frac{16}{64}=\frac{19}{32}\;. $$