Question

One of the basic motivations behind the Minimum Spanning Tree Problem is the goal of designing a spanning network for a set of nodes with minimum total cost. Here we explore another type of objective: designing a spanning network for which the most expensive edge is as cheap as possible.

Specifically, let G = (V, E) be a connected graph with n vertices, m edges, and positive edges costs that are all distinct. Let T = (V, E0 ) be a spanning tree of G; we define the bottleneck edge of T to be the edge of T with the greatest cost.

A spanning tree T of G is a minimum-bottleneck spanning tree if there is no spanning tree T 0 of G with a cheaper bottleneck edge.

(a) Is every minimum-bottleneck tree of G a minimum spanning tree of G? Prove or give a counterexample.

(b) Is every minimum spanning tree of G a minimum-bottleneck tree of G? Prove or give a counterexample.

Answer 1

Solution

a)

This is false.

Let G have vertices {v1, v2, v3, v4}, with edges between each pair of vertices,and with the weight on the edge from v_i to v_j equal to i+j. Then every tree has a bottleneck edge of weight at least 5, so the tree consisting of a path through vertices v3, v2, v1, v4 is a minimum bottleneck tree.It is not a minimum spanning tree, however, since its total weight is greater than that of the tree with edges from v1 to every other vertex

b)

This is true.

Suppose that T is a minimum spanning tree of G, and T’ is a spanning tree with lighter bottleneck edge. Thus,T contains an edge e that is heavier than every edge in T’. So if we add e to T’, it forms a cycle C on which it is the heaviest edge (since all other edges in C belong to T’). By the Cut Property,then,e does not belong to any minimum spanning tree, contradicting the fact that it is in T and T is a minimum spanning tree

--

all the best