# Minimum Spanning Tree - How to Prove this Inequality?

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.

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.
• Thanks for the hint! But can you please illustrate more on your definition of "optimal"? How do you handle the 2 cases that <$f_{m+1}$ is in $e_1,\cdots,e_m$> or <$f_{m+1}$ forms a cycle with $e_1,\cdots,e_m$>? – JrZ Mar 3 '18 at 5:26