Reference no: EM131576452

Question: Suppose that to generate a random simple graph with n vertices we first choose a real number p with 0 ≤ p ≤ 1. For each of the C(n, 2) pairs of distinct vertices we generate a random number x between 0 and 1. If 0 ≤ x ≤ p, we connect these two vertices with an edge; otherwise these vertices are not connected.

a) What is the probability that a graph with m edges where 0 ≤ m ≤ C(n, 2) is generated?

b) What is the expected number of edges in a randomly generated graph with n vertices if each edge is included with probability p?

c) Show that if p = 1/2 then every simple graph with n vertices is equally likely to be generated

A property retained whenever additional edges are added to a simple graph (without adding vertices) is called monotone increasing, and a property that is retained whenever edges are removed from a simple graph (without removing vertices) is called monotone decreasing.