1
$\begingroup$

In a random graph $G(n,M)$ where $n$ is the number of vertices and $M$ the number of edges, prove that as $n$ tends to infinity $P(G(n,M))=H(n,M))=1$ where $H$ is a graph with $M$ independent edges and $n-2M$ isolated vertices.

This is a problem from Bollobas. I find it intuitively obvious. I tried to do it by calculations but failed.

1 Answers 1

2

Fix $M$ and assume one draws uniformly at random with replacement $M$ pairs of objects among $n$. The probability $p_n$ that no object appears twice or more in the sample of $M$ pairs is $ p_n=\prod_{k=0}^{M-1}\frac{{n-2k\choose2}}{{n\choose 2}}=\frac{n!}{(n-2M)!n^M(n-1)^M}\geqslant\left(1-\frac{2M}n\right)^{2M}. $ Thus $p_n\to1$ when $n\to\infty$. Since $p_n$ is the probability that the $M$ edges of $G(n,M)$ have no vertex in common, one sees that, with probability $1-o(1)$, $G(n,M)$ is made of $M$ isolated edges and of $n-2M$ isolated vertices.