Let G = (V, E) be a unit-capacity graph with n vertices and m edges. In this question, we will revisit the randomized edge contraction algorithm for the global min-cut problem we saw in class. In this setting, the contraction algorithm will do one additional contraction so that the final graph is just a single vertex (instead of being left with two vertices which define a cut). (a) Show that in any run of the edge contraction algorithm, the edges contracted form a spanning tree of G (b) Using the analysis we saw in class for the contraction algorithm, argue that there are O(n^2) global min-cuts in any graph (c) Observe that part (c) implies nothing about the number of s-t min-cuts there can be for two vertices s, t elementof V. Give an example of a graph where there are w(n^2) s-t min-cuts for a particular pair of vertices s and t. Recall that a function g(n) = w(n^2) if g(n) is strictly greater than n^2 asymptotically, i.e., g(n) = Ohm (n^2) but g(n) notequalto (n^2) (so functions like n^3, n^10, 2^n, etc.) Note that this counterexample needs to be constructed based on a general parameter n since we are attempting to show an asymptotic lower bound. This means you should describe a graph with n vertices, define the edge set, and then argue why there are w(n^2) min-cuts. Let G = (V, E) be a unit-capacity graph with n vertices and m edges. In this question, we will revisit the randomized edge contraction algorithm for the global min-cut problem we saw in class. In this setting, the contraction algorithm will do one additional contraction so that the final graph is just a single vertex (instead of being left with two vertices which define a cut). (a) Show that in any run of the edge contraction algorithm, the edges contracted form a spanning tree of G (b) Using the analysis we saw in class for the contraction algorithm, argue that there are O(n^2) global min-cuts in any graph (c) Observe that part (c) implies nothing about the number of s-t min-cuts there can be for two vertices s, t elementof V. Give an example of a graph where there are w(n^2) s-t min-cuts for a particular pair of vertices s and t. Recall that a function g(n) = w(n^2) if g(n) is strictly greater than n^2 asymptotically, i.e., g(n) = Ohm (n^2) but g(n) notequalto (n^2) (so functions like n^3, n^10, 2^n, etc.) Note that this counterexample needs to be constructed based on a general parameter n since we are attempting to show an asymptotic lower bound. This means you should describe a graph with n vertices, define the edge set, and then argue why there are w(n^2) min-cuts