Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
How many vertices? – Did Sep 19 '12 at 20:29
Does your exhaustive research include works such as On the Evolution of Random Graphs by Erdös and Rényi (1960)? – Henning Makholm Sep 19 '12 at 20:36

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.