In the classic Erds-Renyi random graph model, we build a random graph on (V) vertices by including

In the classic Erdös-Renyi random graph model, we build a random graph on \(V\) vertices by including each possible edge with probability \(p\), independently of the other edges. Compose a Graph client to verify the following properties:

- Connectivity thresholds: If \(p<1 / V\) and \(V\) is large, then most of the connected components are small, with the largest being logarithmic in size. If \(p>1 / V\), then there is almost surely a giant component containing almost all vertices. If \(p<\ln V / V\), the graph is disconnected with high probability; if \(p>\ln V / V\), the graph is connected with high probability.

- Distribution of degrees: The distribution of degrees follows a binomial distribution, centered on the average, so most vertices have similar degrees. The probability that a vertex is adjacent to \(k\) other vertices decreases exponentially in \(k\).

- No hubs: The maximum vertex degree when \(p\) is a constant is at most logarithmic in \(V\).

- No local clustering: The cluster coefficient is close to 0 if the graph is sparse and connected. Random graphs are not small-world graphs.

- Short path lengths: If \(p>\ln V / V\), then the diameter of the graph (see EXERCISE 4.5.40) is logarithmic.