Redefine the weight of a spanning tree to be the weight of the maximum weight edge in the tree (i.e. the weight of the tree is no longer the sum of the weights of all the edges in the tree, only the weight of the edge with the maximum weight). How would you derive an efficient algorithm to compute the minimum weight spanning tree under this new definition? Do not assume the edge weights are distinct.
A brute force approach would obviously be to compute all possible MSTs, then sort them based on their maximum weighted edge, and choose the smallest one. This is not efficient however, but I am having trouble seeing how to do this. Any ideas?
An algorithm to do this is to repeatedly remove the largest edge. Take the graph $G$ and remove the edge with maximum weight, if the graph doesn't become disconnected. Repeat for second maximum third maximum and so on. The algorithm has complexity $O(|E|^2)$.