For a random graph G(n,p), I can understand how to calculate the E(X) where X is the number of isolated vertices. However, in the case of fixed N edges (N = cn), I am not sure how to proceed in the same calculation of E(X). I don't think finding p = N/$ \binom n2$ would work since that would only give number of edges around N, not exactly N.
What I considered was proceeding by find the probability that a vertex has at least one edge, which I think should be $\frac{n}{n(n-1)/2} = \frac{2}{n-1}$. However this looks wrong to me since this would give >1 probability when n=2. I am not sure how to go ahead, any hint would be very helpful.
[Math] Expected number of isolated vertices for random graph G(n, N)
random-graphs
Best Answer
For each vertex $v$, define the random variable $X_v$ that is 1 if $v$ has degree $0$ and $0$ otherwise.
Then, $\mathbb{E}(X_v) = \mathbb{P}(X_v = 1)$, where the probability is the fraction of random selections of $k$ edges that leave $v$ isolated, over all possible selections of $k$ edges.
$$\mathbb{P}(X_v = 1) = \frac{\binom{\frac{n(n-1)}{2}-(n-1)}{k}}{\binom{\frac{n(n-1)}{2}}{k}} = \frac{\binom{\frac{(n-1)(n-2)}{2}}{k}}{\binom{\frac{n(n-1)}{2}}{k}}$$
Then, by linearity of expectation, the number of isolated vertices is $n\mathbb{E}(X_v)$.
Note that this does make sense for small examples. For instance if $n = 2, k= 1$, we have an expectation of $2\frac{\binom{0}{1}}{\binom{1}{1}} = 0$ isolated vertices, while for $n = 2, k=0$, the expectation is $2\frac{\binom{0}{0}}{\binom{1}{0}} = 2$. If $n = 3, k=1$, we get an expectation of one isolated vertex, etc.