# Graph Theory mixed with probability - hard question

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?

-
–  Artem Dec 13 '12 at 1:47
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

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$?

-
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
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