TITLE: For a graph G with uniquely-weighed edges, prove there isn't a spanning tree in which every edge has less weight than the maximal edge of an MST of G.
QUESTION [2 upvotes]: Let G be connected undirected graph where every edge of G has a unique weight. Let T be an MST of G s.t. w is the weight of the highest-weighed edge in T.
Prove that there does not exist a spanning tree of G where the weight of every edge is less than w.
I've tried solving this by contradiction, assuming there is such a spanning tree and then using that to show that this implies T cannot be a MST, but I find myself lost when it comes to figuring out the finer details.
I'm looking for more of a starting point to a solution rather than a full solution, so that I can try to solve at least part of it myself, but any kind of help would be much appreciated.

REPLY [1 votes]: A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Hint: If all of the edges in the spanning tree $T$ have less than the weight of the maximal edge of the proposed MST, can you construct a better tree by replacing the maximal edge of the MST with one of the edges in $T$?
Hint: What would it mean if you could create a tree with a lower total weight than the proposed MST?
Hint: What does the requirement of unique edge weights mean for the graph and the MST in relation to this question?
{"set_name": "stack_exchange", "score": 2, "question_id": 2029222}