This is a question from "Algorithm Design", chapter 4 question 19: https://www.chegg.com/homework-help/Algorithm-Design-1st-edition-chapter-4-problem-19E-solution-9780321295354

A group of network designers at the communications company CluNet find themselves facing the following problem. They have a connected graph G = (V, E), in which the nodes represent sites that want to communicate. Each edge e is a communication link, with a given available bandwidth b_e.

For each pair of nodes u, v V, they want to select a single u-v path P on which this pair will communicate. The bottleneck rate b(P) of this path P is the minimum bandwidth of any edge it contains; that is, b(P) = min_epb_e. The best achievable bottleneck rate for the pair u, v in G is simply the maximum, over all u-v paths P in G, of the value b(P).

Its getting to be very complicated to keep track of a path for each pair of nodes, and so one of the network designers makes a bold suggestion: Maybe one can find a spanning tree T of G so that for every pair of nodes u, v, the unique u-v path in the tree actually attains the best achievable bottleneck rate for u, v in G. (In other words, even if you could choose any u-v path in the whole graph, you couldnt do better than the u-v path In T.)

This idea is roundly heckled in the offices of CluNet for a few days, and theres a natural reason for the skepticism: each pair of nodes might want a very different-looking path to maximize its bottleneck rate; why should there be a single tree that simultaneously makes everybody happy? But after some failed attempts to rule out the idea, people begin to suspect it could be possible.

Show that such a tree exists, and give an efficient algorithm to find one. That is, give an algorithm constructing a spanning tree T in which, for each u, v V, the bottleneck rate of the u-v path in T is equal to the best achievable bottleneck rate for the pair u, v in G.

Plus: Please prove: If the bandwidths are unique (i.e. no every link has a different bandwidth), then the tree you construct is unique also.

Thank you