Problem $2.$ Maximum clearance routes

Every year, trucks get stuck on Storrow Drive because of the low bridges $($sometimes called "storrowing"$).$ Suppose you're running a trucking company in Boston with $\backslash ($ n $\backslash )$ warehouses. Each section of road $\backslash ($ e $\backslash$in E $\backslash )$ will be annotated with the clearance of the lowest bridge on that portion of road $\backslash ($ c$\_\{$e$\}\backslash ).$ Assume all of the roads are undirected, and that all of the clearances are unique. We'll say that the clearance of a route from $\backslash ($ i $\backslash )$ to $\backslash ($ j $\backslash )$ is the minimum clearance of all the road segments on the route $($you can't drive a truck that's taller than the lowest bridge on the route$).$ Next, we'll say that a route is a maximum$-$clearance route between $\backslash ($ i $\backslash )$ and $\backslash ($ j $\backslash )$ if it is the route between $\backslash ($ i $\backslash )$ and $\backslash ($ j $\backslash )$ with largest route clearance out of all possible routes from $\backslash ($ i $\backslash )$ to $\backslash ($ j $\backslash ).$ Intuitively, the maximum$-$clearance route between two nodes tells you the tallest truck that you can drive between the two locations without getting stuck under a bridge, as well as which path to use.

You want to find an algorithm that computes a tree for max$-$clearance routes from a given node $\backslash ($ s $\backslash ).$ After giving it some thought, you think it might be related to the idea of a maximum spanning tree with respect to the edge clearances.

Note: the maximum spanning tree of a graph $\backslash ($ G $\backslash )$ is just a tree that connects all vertices in $\backslash ($ G $\backslash )($hence "spanning"$)$ while maximizing the sum of the edge weights in the tree. Cycles are not allowed, as we still want a tree.

$1.$ State the cut and cycle property for maximum spanning trees $($MaxST$).$

$2.$ Show that in any graph $\backslash ($ G $\backslash )$ with unique edge clearances, the path given by using edges from the maximum spanning tree of G $($with respect to the edge weights given by the clearances $\backslash ($ c$\_\{$e$\}\backslash ))$ gives the maximum clearance route between any two warehouses. $[$Hint: There are a couple of natural ways to do this. One way is to proceed by contradiction: suppose that the highest$-$clearance path is not part of the MaxST; show that together with edges in the MaxST it creates a cycle that contradicts the cycle property above.$]$

$3.$ Give a polynomial$-$time algorithm that takes a graph $\backslash ($ G $\backslash )$ with distinct edge clearances and outputs the maximum spanning tree. Hint: Modify any of the minimum$-$weight spanning tree algorithms from class.