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$
4
  • $\begingroup$ What did you try? $\endgroup$ Commented Jan 29, 2018 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$ Commented Jan 29, 2018 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$ Commented Jan 29, 2018 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.
    Commented Jan 29, 2018 at 16:28

1 Answer 1

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 and acknowledge you have read our privacy policy.

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