47.1k views
1 vote
) is every minimum bottleneck tree of g a minimum spanning tree of g? prove or give a counter example

1 Answer

6 votes

The answer is false. To explain further, let G have vertices {v1, v2, v3, v4}, with ends between each pair of vertices, and with the mass on the edge from vi to vj equal to I + j. Then each tree has a bottle neck edge mass of as a minimum of 5, so the tree containing of a track through vertices v3, v2, v1,v4 is a least bottleneck tree. It is not a least spanning tree, though, subsequently its total mass is greater than that of the tree with edges from v1 to every single vertex.

User Lefteris
by
8.2k points