Consider the following reverse greedy algorithm for the spanning tree problem: we start with the input graph G, and in each step, remove the edge of the largest weight that does not disconnect G. The algorithm terminates when there is no such edge (i.e., what remains is a tree). Prove that this algorithm also finds the minimum weight spanning tree Hint: Argue one step at a time (i.e., that the cost of the MST is preserved in each step). Prove this by contradiction. You may also want to use the observation that removing any edge of a tree divides the set of vertices it into two connected pieces. ]