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.

  • $\begingroup$ 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$>? $\endgroup$ – JrZ Mar 3 '18 at 5:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.