Algorithm-METest-MST

Question

A Spanning tree T(V,E)  has bottleneck edge, means all edges present in T with the greatest cost would be bottleneck edges.

Now they have said, A spanning tree T of G is a minimum bottleneck spanning tree if no spanning tree T' existed with cheaper bottleneck edge- I think overall this means Tree T is minimum bottleneck spanning tree, if no Tree T' existed such that $Cost(T') \lt Cost(T)$ and that is actually the definitions of a minimum MST.

I thought S1 should be true in addition to S2, but in the answer, S1 is claimed to be false.

S1: Every minimum bottleneck spanning tree of G is a minimum spanning tree of G: I think this must be true because let us assume T is a minimum bottleneck tree of G with bottleneck edge(edge with highest cost) $e_i$. This tree is minimum because there does not exist a tree T' which can replace edge $e_i$ by $e_j$ such that $cost(e_j) \lt cost(e_i)$. If this holds true, then by definition of Minimum MST, this tree T is also the minimum spanning tree for graph G otherwise some other tree T' would have existed who has edge $e_j$ and it could have replaced $e_i$ in T to produce tree T', thereby contradicting the assumption that T' is a minimum bottleneck spanning tree of G.

Below is the solution given by them in support of S1

I think if in (A) it was minimum bottleneck spanning tree, then (B) would not have been possible to produce.

Please guide.

Comments

Although I didn't read the entire question, their example is incorrect - the question says distinct weights and they've used five twice.

---

Ayush Upadhyaya one quick thought

Consider all the edge weights are same and one edge is designated as "bottleneck edge" .

In this case s1 will be false in every other case s1 should be true i guess.

 

---

@Hemanth-Graph has distinct positive edge weights.

---

Yeah  Ayush Upadhyaya, i looked that after answering the question :P.

But i said

"every other case s1 should be true i guess."