0
$\begingroup$

Consider the Minimum Spanning Tree Problem on an undirected graph G = (V, E), with a cost ≥ 0 on each edge, where the costs may not all be different. If the costs are not all distinct, there can in general be many distinct minimum-cost solutions. Suppose we are given a spanning tree T ⊆ E with the guarantee that for every e ∈ T, e belongs to some minimum-cost spanning tree in G. Can we conclude that T itself must be a minimum-cost spanning tree in G? Give a proof or a counterexample with explanation.

$\endgroup$
0
$\begingroup$

Here is the simplest counterexample. The edge set $\{10, 12\}$ is not a minimum spanning tree (MST). However, edge 10 is in the edge set $\{10, 02\}$, an MST. Edge 12 is in the edge set $\{12, 02\}$, an MST.

graph made using graphonline.ru/en/


Note that there are two edges of equal weight in the above counterexample.

(Question.) What if no edges have the same weight?

$\endgroup$
0
$\begingroup$

Consider the following non-minimum spanning tree.

           1
 +-------------------+
 |                   |
 |                   |
 |                   |
2|←                 →|2
 |                   |
 |                   |
 |         ↓         |
 +-------------------+
           1
$\endgroup$
  • $\begingroup$ Could you please elaborate? $\endgroup$ – csGeek Dec 5 '18 at 23:51

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.