0
$\begingroup$

I cant proof that if f is the heaviest edge in weight from all the other edges in the circle which it is a part of, then f will not participate in any Minimum Spanning Tree. please help.

$\endgroup$
2
  • $\begingroup$ This might be considered as wrong. For example, consider a triangle with the same weight on all three edges. $\endgroup$
    – John L.
    Commented Aug 28, 2021 at 0:40
  • $\begingroup$ Does this answer your question? What edges are not in any MST? $\endgroup$
    – John L.
    Commented Aug 28, 2021 at 0:42

1 Answer 1

0
$\begingroup$

Lets assume that it did participate in an MST $T$.

Now, removing $f$ will split $T$ into two connected components - $T_1,T_2$. In particular, both vertices of $f$ need to be in different connected components. Lets call the vertices $v_1$ and $v_k$, and w.l.o.g. assume $v_1\in T_1$ and $v_k\in T_2$.

Lets name all vertices in the cycle by $v_1,v_2,\dots,v_k$ such that there is an edge between $v_i$ and $v_{i+1}$ for all $i$ (and of course, $v_1,v_k$ are the vertices of $f$).

Since $v_1\in T_1$ and $v_k\in T_2$, and also $v_i\in T_1\lor v_i\in T_2$ then there must be some index $i_0<k$ with $v_{i_0}\in T_1$ and $v_{i_0+1}\in T_2$. We know that $(v_{i_0} , v_{i_0 + 1})$ is an edge in $G$, and its weight is lower than that of $f$ - and in addition it will connect the two components! Therefore, by replacing $f$ with this edge we get another spanning tree with a lower weight, which is a contradiction to the assumption we started with an MST!

$\endgroup$
2
  • $\begingroup$ thank you very much,you are brilliant, I really appricitate youre quick and full response sir, I fully understand now. $\endgroup$ Commented Aug 27, 2021 at 21:27
  • $\begingroup$ Glad I can help :) $\endgroup$
    – nir shahar
    Commented Aug 27, 2021 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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