Question

Suppose that to generate a random simple graph with n vertices we first choose a real number p with\({\bf{0}} \le {\bf{p}} \le {\bf{1}}\). For each of the\({\bf{C}}\left( {{\bf{n,2}}} \right)\)pairs of distinct vertices we generate a random number x between 0 and 1.

If\({\bf{0}} \le {\bf{x}} \le {\bf{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\({\bf{0}} \le {\bf{m}} \le {\bf{C}}\left( {{\bf{n,2}}} \right)\)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\({\bf{p = }}\frac{{\bf{1}}}{{\bf{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.

Short answer

(a) The value obtained is \(C\left( {n,m} \right){P^m}\left( {1 - P} \right)\).

(b) The expected number is \(np\).

(c) All labelled graphs are equally likely.

Step-by-step solution

 Introduction

A vertex (or node) of a graph is one of the objects that are connected together. The connections between the vertices are called edges or links.

(a) Find the value

It have for a complete graph\(G\)having\(m\)edges where\(0 \le m \le C\left( {n,2} \right)\). Then the required probability is given by:\(C\left( {n,m} \right){P^m}\left( {1 - P} \right)\).

Hence, the value obtained is \(C\left( {n,m} \right){P^m}\left( {1 - P} \right)\).

(b) Find the expected number

Let us take a graph\(G\)having\(n\)vertices.

Expected number is given by\(np\).

Hence, the expected number is \(np\).

(c) Find the graph

Let us take a simple graph\(G\)having\(n\). It need to generate a labelled graph

\(G\),so it need to pair up the vertices and need to apply the process to them, then need to apply the process to them, then need to choose a random number \(x\)with the condition that\(x \le \frac{1}{2}\)(\(G\)has an edge between that pair of vertices) and\( \ge \frac{1}{2}\)(\(G\)has no edge).

Hence, the probability of making the right selection is equal for each edge and\(\frac{1}{2}C\left( {n,2} \right)\)overall.

Hence, all labelled graphs are equally likely.