# expected number of nodes with degree two?

## 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}$$

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.

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