0
$\begingroup$

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


I was only able to find the probability of any vertex having degree 2. Let me explain what I tried. For any vertex we can have n-1 edges connecting it(since its a simple graph), so for it to have degree = 2, two of these n-1 edges should be there, and rest not.

This gives: $\binom{n−2}{2}p^2(1−p)^{n−3}$.

$\endgroup$
  • $\begingroup$ What did you try? $\endgroup$ – Curious_Dim Jan 29 '18 at 15:24
  • $\begingroup$ I was only able to find the probability of any vertex having degree 2. Let me explain what I tried. For any vertex we can have n-1 edges connecting it(simple graph), so for it to have degree = 2, two of these n-1 edges should be there, and rest not. This gives $\binom{n-1}{2}p^2(1-p)^{n-3}$. $\endgroup$ – Rishabh Gupta Jan 29 '18 at 15:36
  • $\begingroup$ That is correct, but I think from that point you can not just add up this probability $n$ times because the degree of each vertex is not independent from each other vertex $\endgroup$ – Curious_Dim Jan 29 '18 at 15:49
  • $\begingroup$ I suggest you edit the question to incorporate that information into the question. We want questions to be self-contained, so people don't have to read the comments. And the more you can give us about what progress you've made and where you got stuck, the more likely we can give you an answer that will help you (and if you show that you've exhausted all reasonable options to help yourself, that might make others more likely to help you). $\endgroup$ – D.W. Jan 29 '18 at 16:28
1
$\begingroup$

Hint:

Indicator random variables.

If that's not enough and you need a second hint:

Use linearity of expectation.

$\endgroup$

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.