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 < 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

• "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)?

StackExchange Computer Science Q#100964, answer score: 2