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

Improve this question
$\endgroup$
4
  • $\begingroup$ What did you try? $\endgroup$
    – Curious_Dim
    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$
    – Rishabh Gupta
    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$
    – Curious_Dim
    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. ♦
    Jan 29, 2018 at 16:28

1 Answer 1

Reset to default
1
$\begingroup$

Hint:

Indicator random variables.

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

Use linearity of expectation.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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