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?
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)$$