Consider the following alternative scheme for computing a global mincut of an undirected graph G = (V, E): In each iteration, we choose two nodes at random and contract them, where contract(v, w) simply merges v and w into a supernode, which inherits all edges previously incident to either v or w. (Any edges connecting v to w disappear.) We repeat this until exactly two supernodes remain, at which point we output all the edges between those nodes as our global mincut. Either prove that this variant also computes a global mincut with high probability (possibly by running multiple times) in polynomial time, or prove that it fails with a very high probability and cannot find a mincut in polynomial time. Consider the following alternative scheme for computing a global mincut of an undirected graph G = (V, E): In each iteration, we choose two nodes at random and contract them, where contract(v, w) simply merges v and w into a supernode, which inherits all edges previously incident to either v or w. (Any edges connecting v to w disappear.) We repeat this until exactly two supernodes remain, at which point we output all the edges between those nodes as our global mincut. Either prove that this variant also computes a global mincut with high probability (possibly by running multiple times) in polynomial time, or prove that it fails with a very high probability and cannot find a mincut in polynomial time