0
$\begingroup$

Given an un-directed and connected graph $G$ and two spanning trees $T1$, and $T2$

whereas:

$T1$ is an MST and an ordered list of it's edges by their weight is: $ {a_1 <= a_2 ....=<a_n }$

$T2$ is a random spanning tree of $G$ and an ordered list of it's edges by their weight is: $ {b_1 <= b_2 ....=<b_n }$

I need to prove that for every edge $ a_i<= b_i$

I tried doing so by induction by got stuck. Any help will be appreciative. Thanks!

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.