1
$\begingroup$

Question

$\text{A simple graph with n vertices is constructed by randomly and independently placing an }$ $\text{edge between every two vertices with probability p. What is the expected number of nodes }$ $\text{ with degree two?}$

My Approach

For $2$ degree there must be $2$ edges from a vertex.

Therefore expectation

$$=n \times p \times p +(n-1)\times p \times p + ...1 \times p \times p$$

$$=p^{2} \times \frac{n \times (n-1)}{2}$$

Is it correct?please help

$\endgroup$
2
$\begingroup$

Guide:

We are working with a simple graph with $n$ nodes.

Let's introduce an indicator variable $X_i$ that takes value $1$ is its degree is $2$ and takes value $0$ otherwise.

$$P(X_i=1)=\binom{n-1}{2}p^2(1-p)^{n-1-2}$$

That is

$$E(X_i)=\binom{n-1}{2}p^2(1-p)^{n-3}$$

The expected number of nodes with degree $2$ would be $\sum_{i=1}^n E[X_i]$. Hopefully you can take it from here.

$\endgroup$
  • $\begingroup$ thanks a lot.Can you please share some resources regarding indicator random variable ?i am unable to find any $\endgroup$ – laura Jul 17 '18 at 11:20
  • $\begingroup$ here is one. $\endgroup$ – Siong Thye Goh Jul 17 '18 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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