POJ 2485 - Highways
Problem : Find a spanning tree to make the longest edge minimum.
Solution : The longest edge of MST is the answer.
Proof : If it's not the case. Let E1 is the different edge of MST from the answer spanning tree, and E2 is the edges MST doesn't have but answer does. Then get (e1=max(E1))<E2. Since there is a perfect match from E1 to E2 for first displace, let e2 to be the match of e1. Obviously, e2<e1. Thus cut e1 and connect e2 get a smaller spanning tree than MST. Contradiction. []