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?
I have no idea about this question,
$\endgroup$ 22 Answers
$\begingroup$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$?
$\endgroup$ 3 $\begingroup$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
$\endgroup$
