Expected number of vertices of degree k in a random graph

653 Views Asked by At

I am wondering what would be the expected number of vertices with degree k in the random graph $G(n,p)$?

What I have gotten so far is: $$\mathbb{P}(deg(v)=k)=\binom{n-1}{k}p^k(1-p)^k $$ So then the number of vertices with exactly $k$ degrees would be: $$n\binom{n-1}{k}p^k(1-p)^k$$

I know that it is possible to simplify this more but I am not sure if this is right or how to simplify.

1

There are 1 best solutions below

0
On

As pointed out in a comment, the first equation is wrong. The probability for exactly $k$ out of $n-1$ edges to exist is

$$ \binom{n-1}kp^k(1-p)^{n-1-k}\;, $$

so the expected number of vertices of degree $k$ is

$$ n\binom{n-1}kp^k(1-p)^{n-1-k}\;. $$

No simplification is possible (unless you regard $n\binom{n-1}k=(n-k)\binom nk$ as a simplification).