Expected number of isolated vertices for random graph G(n, N)

Question

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.

Answer 1

You have $n$ points and $m$ edges ($0<m<\binom{n}{2}$); and all possible graphs of that kind can form with no bias (equal probability).

There are $\dbinom{\binom{n}{2}}{m}$ possible graphs that can form.

For any particular node, #$k$, there are $\dbinom{\binom{n-1}{2}}{m}$ graphs that can form that isolate node.

Eg : $n=4$ $M=2$, there are $\binom{6}{2}$, or $15$ possible graphs, and $3$ of these isolate node #$2$

Take it from there...

Answer 2

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.