You are free to use any programming language, as well as any built-in implementation of a Gomory-Hu ...

---

You are free to use any programming language, as well as any built-in implementation of a Gomory-Hu tree. A random graph G(n, p) is a graph in which each edge occurs independently with probability p. (a) Prove that G(n, p) for p = 5 log n / n is connected with probability at least 1 - 1/n. (Hint: perform a separate analysis for all partitions of size (i, n - i), i in [1, n/2].) (b) Argue that with probability at least 1 - 1/n, the Gomory-Hu tree of G(n, p) for p = Theta(k log n)/n has all edges of weight k or more. (c) Perform an experimental analysis of the k-edge-connected components in G(n, p), for a large collection of choices for k and p and an appropriately large integer n, to estimate: the size of the largest k-edge-connected component; the number of k-edge-connected components; and the inflection point(s) for the probability p around which the number of k-edge-connected components seems to change by a large value.