2
$\begingroup$

If I have a random graph with $ \mathbb{P}\left[(v_1,v_2) \in E\right] = 50\% \quad \forall v_1,v_2 \in V. $

How would I speculate the amount of connected components that random graph may have?

I have exhaustively read and researched this question and come to find that I cannot come up with a reasonable answer. I come to the conclusion that I need help.

I know that the use of the Poisson distribution and the arbitrary distribution of of vertex degree can be implemented into this concept, and that that a random graph is a collection of points on vertices with lines or edges, connecting pairs of them at random. The 50% being set in E could be the split of the connected pairs?

  • 3
    Does your exhaustive research include works such as [On the Evolution of Random Graphs](http://www.renyi.hu/~p_erdos/1960-10.pdf) by Erdös and Rényi (1960)?2012-09-19

1 Answers 1

2

In Diestel's Graph Theory, in section on Random Graphs, he argues (Corollary 11.3.3) that for every constant $p \in (0,1)$ and every integer $k$, almost every graph in $\mathcal{G}(n,p)$ is $k$-connected, which implies that it has one connected component.