Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose we wish to construct a graph in the following manner: Denote the vertices of the graph as $1,2,\dots,n$. For every pair $\{i,j\}$, we flip a fair coin. If it comes up tails, $\{i,j\}$ is an edge of the graph; if it comes up heads, $\{i,j\}$ is not an edge of the graph. Please answer the following:

a. What is the probability that the graph we end up with is a complete graph (i.e., $K_n$) ?

b. Let $D_1$ denote the degree of vertex $1$, What is $\Bbb E[D_1]$, the expected degree of vertex $1$?

c. Notice that the expected degrees of vertices $2,\dots,n$ should also be the same as that of vertex $1$. Given this observation, and the handshaking lemma, what is the expected number of edges in the graph?

I have no idea about this question,

share|improve this question
1  
See Erdős–Rényi model –  Artem Dec 13 '12 at 1:47
1  
No idea? To get the complete graph, every flip must come up tails, right? You can't compute this probability? –  Gerry Myerson Dec 13 '12 at 1:47

2 Answers 2

up vote 2 down vote accepted

HINTS:

(a) In order to get a complete graph, the coin has to come up tails every time; if there are $m$ edges, that event has probability $\left(\frac12\right)^m$. What is $m$?

(b) The possible degrees of vertex $1$ are $0,1,\dots,n-1$. Let $p_k$ be the probability that $D_1=k$; then by definition

$$\Bbb E[D_1]=\sum_{k=0}^{n-1}kp_k\;,$$

so you just need to calculate the $p_k$ and evaluate the sum. In order to get degree $k$, you must flip tails $k$ times and heads $(n-1)-k$ times for the $n-1$ potential edges at vertex $1$, and there are $\binom{n-1}k$ possible sets of $k$ edges. Can you put the pieces together to get $p_k$?

share|improve this answer
    
Thanks, I am new in graph theory and I didn't know where to start, thanks –  Hooman Dec 13 '12 at 1:54
    
@Hooman: You’re welcome. I think that I gave enough of a hint to give you a good start, but if you get stuck, just leave a comment. –  Brian M. Scott Dec 13 '12 at 1:55
    
This was very interesting problem ,it makes much more sense now –  Hooman Dec 13 '12 at 2:24

To complete Brian's hints. Here is a hint for (c):

The handshaking lemma refers to the fact that the sum of the vertex degrees equals twice the number of edges. So you have $$\text{expected number of edges}=\frac{ \mathbb{E}[D_1+D_2+\cdots + D_n]}{2}.$$ Use the linearity of expectation to evaluate this expression. Notice that the number of edges is a binomial distribution. You might check your answer against what is known about the expected value of a binomial distribution

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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