-1
$\begingroup$

Let G be undirected graph, G=(V,E), and all edge weights are distinct. Consider an edge e=(u,v)∈E that wasn't included in the solution obtained from applying Kruskal Algorithm to G. Prove that this edge isn't in any Minimimum Spanning Tree of G.

Improve this question
$\endgroup$
4
  • $\begingroup$ Do you perhaps also have that all edge weights are distinct? $\endgroup$ – JimN Sep 6 '20 at 23:05
  • $\begingroup$ Yes, all edge weights are distinct. $\endgroup$ – Kate Austen Sep 6 '20 at 23:32
  • $\begingroup$ You should probably include that In your first sentence in your question statement $\endgroup$ – JimN Sep 7 '20 at 0:01
  • $\begingroup$ If this is quoted content, please attribute it properly - hyperlink welcome. Consider using a block quote (see, e.g, post editor tool bar "quotation mark button (")). $\endgroup$ – greybeard Sep 7 '20 at 14:17
0
$\begingroup$

Without additional assumptions about the edge weights that's false. A simple counterexample is a triangle graph where all edge weights are equal.

Improve this answer
$\endgroup$

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.