# How to find spanning tree of a graph that minimizes the maximum edge weight?

Suppose we have a graph G. How can we find a spanning tree that minimizes the maximum weight of all the edges in the tree? I am convinced that by simply finding an MST of G would suffice, but I am having a lot of trouble proving that my idea is actually correct. Can anyone show me a proof sketch or give me some hints as to how to construct the proof? Thanks!

• Try to construct a counterexample. Not sure that one exists, but for a moment I felt that one does. In any case, this is a good proof strategy. – Dave Clarke Jun 4 '12 at 16:39
• en.wikipedia.org/wiki/… – Jukka Suomela Jun 4 '12 at 16:52
• If you know Kruskal’s algorithm for the minimum spanning tree, it is an easy exercise to show that the output of Kruskal’s algorithm is a minimum bottleneck spanning tree. (I think that it is easier than showing that the output of Kruskal’s algorithm is a minimum spanning tree.) – Tsuyoshi Ito Jun 4 '12 at 17:39
• @AdenDong if you solved your own question, feel free to self-answer. – Artem Kaznatcheev Jun 5 '12 at 0:47
• @DaveClarke: "In any case, this is a good proof strategy." -- True. Worked for me. TCS/maths education should focus way more on this back and forth that is inherent to the process. – Raphael Jun 5 '12 at 11:15

Given a graph $G(V, A)$, we know that any spanning tree contains an edge in every cutset. Let $S_{min}^{max}$ and $S$ be the minimax weight spanning tree of $G$ and minimum weight spanning tree of $G$ resp. Any edge $e \in S$ is associated with a cutset $C$. Corresponding to cutset $C$,$S_{min}^{max}$ must also contain an edge, say $e'$. Then if $w(e') < w(e)$, we know that replacing $e$ with $e'$ in $S$ will produce a new spanning tree with lower overall weight, thus contradicting our assumption of optimality of $S$. Hence, we can see that the weight of every edge in $S$ is no greater than the weight of a corresponding edge (obtained from the cutset) in $S_{min}^{max}$. Since, we have compared every edge in $S$ but perhaps possibly may not have compared every edge of $S_{min}^{max}$ in the above process for comparison, the max weight edge in $S_{min}^{max}$ has to be atleast as much as much as the max weight in $S$. Hence we can conclude that $S$ itself produces a minimax weight spanning tree.