Question 1

Hint: prove that an MST is a minimum bottleneck spanning tree.

Extra challenge: Compute a minimum bottleneck spanning tree in linear time in the worst case. Assume that you can compute the median of n keys in linear time in the worst case.


Question 2

Hint: consider the subgraph G′ of G containing only those edges whose weight is strictly less than that of edge e.



Question 3

Hint: complement of an MST.