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,
Best Answer
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$?