Are edges in a minimum spanning tree not heavier than respective edges in another spanning tree? Let $G$ be an undirected connected weighted graph, and let $T$ be a minimum spanning tree of $G$ with edge weights: $w_1 \le w_2 \le ... \le w_{n-1}$.

Now let $T'$ be some other spanning tree of $G$ (doesn't have to be minimum) with edge weights: $w'_1 \le w'_2 \le ... \le w'_{n-1}$.

I need to prove\disprove the following claim: for every $i$:  $w_i \le w'_i$.

I've tried to find a counterexample, but I wasn't successful. So I'm quite sure the claim is correct. However, I had trouble to prove it formally.  

I assume the contrary, which means there is an $i$ that satisfies $w'_i &lt; w_i$ and I take the first one that does. I tried adding it to the tree $T$ or trying to find a minimum spanning tree with this edge using Kruskal, but no luck.
Here are some hints:


Flesh out your counterexample with quantifiers properly: "There exists a graph $G$, and a minimum spanning tree $T$ for $G$ with edge weights $w_1 \le w_2 \le \dots \le w_{n-1}$, and another spanning tree $T'$ of $G$ with edge weights $w'_1 \le w'_2 \le \dots \le w'_{n-1}$, and an integer $i$ obeying $1 \le i \le n-1$, such that $w'_i &lt; w_i$".  In a situation like this, from the set of all such counterexamples ($(G, T, T', i)$ tuples), you are free to choose one having minimum possible $i$, and it's nearly always useful (and never harmful) to do so.
"I tried adding it to the tree $T$" -- you must first show that it is not already in $T$.  Here you can use minimality of $i$ for edges to the left, and the increasing weight order for edges to the right.
Let's add it to $T$, to make a graph I'll call $G_2$.  What noticeable feature does $G_2$ contain?
What simple modifications could you make to that feature in $G_2$ to turn it back into a tree?  Hint: With this particular feature, there will always be at least 3 ways to do this, and there could be as many as $n$.
Can you choose an option in the previous step that will lead to a tree that is strictly lighter than $T$, and thus a contradiction (since we assumed $T$ to be minimal)?