[Math] Proof involving maximum weight of edge in minimum spanning tree

graph theoryproof-writingtrees

Let $G$ be a minimum spanning tree of a complete graph. Let $e$ be the maximum weight edge in $G$. I'd like to proof that given any other spanning tree $G'$ of this graph, being $j$ the maximum weight edge of $G'$, then $w(e) \leq w(j)$.

I really don't know if this is true, and I can't think of any counterexample to proof the opposite.

Any suggestions?

Best Answer

The cut property of the Minimum Spanning Tree (MST) problem is what you should look at. i.e. Any edge $\{x,y\}$ in an MST has weight at least as small as the edge with smallest weight in the cut that separates $x$ and $y$. This can easily be shown by contradiction.

In any cut which includes the edge $e$ (i.e. separates it's two adjacent vertices), we know that $e$ must be an edge with minimum weight in this cut.

Any spanning tree $G'$ must contain at least one edge in this cut.

Let $e'$ be such an edge. We know that $$w(e') \ge w(e)$$ We also know that $$w(j) \ge w(e')$$ So, $$w(j) \ge w(e') \ge w(e)$$