One of the basic motivations behind the Minimum Spanning Tree Problem is the goa

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 edge costs that you may assume are all distinct. Let T = (V, E) 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 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.

Explanation / Answer

Spanning Trees

Theorem: A graph is connected iff it has a spanning tree.

Proof: If a graph is connected, we can identify a cycle and remove an edge from it: it will still be connected. We can continue this until no cycles remain. The result is a spanning tree.

If we have a graph with a spanning tree, then every pair of vertices is connected in the tree. Since the spanning tree is a subgraph of the original graph, the vertices were connected in the original as well.

Minimum Spanning Trees

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.