Relation between sorted weights of spanning tree and minimal spanning tree Let $ G=(V,E) $ be a graph, $T$ a minimal spanning tree for $G$ and $T'$ some spanning tree of $G$.
Let us denote:
$w_1\leq w_2\leq ... \leq w_{n-1}$ the weights of $T$
$w'_1\leq w'_2\leq ... \leq w'_{n-1}$ the weights of $T'$
Prove/Disprove: for every $i$ the following holds: $w_i \leq w'_i$
====
Need some guidance/help figuring this out. so far I tried disproving for a while but with no success, then I thought maybe I could assume there exists $w'_i <w_i$ and somehow by adding it to $T$ and examining the cycle it creates I could get to a contradiction...
 A: As you requested some guidance/help, I won't go into details (I may do it later if you would like to). Your idea is good, let's suppose there exists an $i$ such that $w_i' < w_i$. Let the edge corresponding to $w_i'$ be $e_i'$. By examining the addition of $e_i'$ to $T$ and the cycle it creates is not enough to get a contradiction, because it can happen that $e_i'$ has the largest weight in that cycle.  
Instead, we can use the simple claim stating that every MST of a graph can be the output of Kruskal's algorithm. Now let $i$ be the smallest of such indices, i.e. it is true that $w_j \leq w_j'$ for all $j < i$ and $w_i > w_i'$. The question you should try to investigate is after putting $i-1$ edges to $T$, how can it happen that Kruskal's algorithm puts $e_i$ to $T$ (where $e_i$ is the edge corresponging to $w_i$)? Using the fact that each of $T$ and $T'$ is a tree you can have a contradiction.  
Edit 1: More details 
Let the subgraph of $T$ spanned by $e_1,...,e_{i-1}$ be denoted by $U$, and let the subgraph of $T'$ spanned by $e_{1}',...,e_{i}'$ be denoted by $U'$. As $T$ and $T'$ are trees, $U$ and $U'$ are forests (not necessarily connected). Let the number of components of $U$ be denoted by $c$, while the number of components of $U'$ is $c'$.  
First note that because the edges are sorted by their weights, $w_{j}' \leq w_{i}' < w_i$ for all $j \leq i$. If Kruskal's algorithm puts $e_i$ to $T$, that means that $U \cup e_{j}'$ must contain a cycle, for all $j \leq i$. This can happen only if all $e_{j}'$ edges are inside the components of $U$ (they cannot be between components because that would not create a cycle in $U$). Hence, $c' \geq c$, and the number of nodes in $U$ must equal to the number of nodes in $U'$ (denoted by $n$).  
As $U$ has $i-1 = n - c$ edges, while $U'$ has $i = n - c'$ edges, this leads to $i-1 = n - c \geq  n - c' = i$, and we have our contradiction (we used the fact that a forest containing $n$ nodes and $c$ components has exactly $n-c$ edges).
