Show that the expected number of empty boxes is (M − 1)N /MN−1.

11. We are provided with a coin which comes up heads with probability p at each toss. Let v1, v2, . . . , vn be n distinct points on a unit circle. We examine each unordered pair vi , v j in turn and toss the coin; if it comes up heads, we join vi and v j by a straight line segment

(called an edge), otherwise we do nothing. The resulting network is called a random graph.

3.6 Problems 49 Prove that