I'm stuck on this problem for a few days:
Given an undirected connected graph $G$, construct a minimum spanning tree $T = \{e_1,e_2,\cdots,e_k\}$ with $w(e_1) \leq w(e_2) \leq \cdots \leq w(e_k)$ by Kruskal's (or Prim's) algorithm. For any spanning tree $T'=\{f_1,f_2,\cdots, f_k\}$ with $w(f_1) \leq w(f_2) \leq \cdots \leq w(f_k)$, show that $w(e_i) \leq w(f_i)$ for all $i\in[1,k]$.
I've been trying to prove this by inducting on $k$. However, the induction step is surprisingly difficult in terms of finding a contradiction. I'd appreciate it if anyone could help.
HINT
WLOG assume $G = (V,E)$ is connected. Then $k = |V| - 1$. Induct on the number of steps in the algorithm, showing that assuming $e_1, \ldots, e_m$ is optimal so is $e_{m+1}$. Use the construction of the algorithm to prove that each consecutive chosen edge is optimal.