In: Advanced Math
Suppose you are given an undirected, connected, weighted graph G. You want to find the heaviest weight set of edges that you can remove from G so that G is still connected. Propose an optimal greedy algorithm for this problem and prove that it is optimal. (Hint: use matroid theory!).