A tight bound on the collection of edges in MSTs of induced subgraphs

摘要

Let G = (V, E) be a complete n-vertex graph with distinct positive edge weights. We prove that for k is an element of {1, 2,..., n - 1}, the set consisting of the edges of all minimum spanning trees (MSTs) over induced subgraphs of G with n - k + 1 vertices has at most nk - (k+12) elements. This proves a conjecture of Goemans and Vondrak [M.X. Goemans. J. Vondrak, Covering minimum spanning trees of random subgraphs. Random Structures Algorithms 29 (3) (2005) 257-276]. We also show that the result is a generalization of Mader's Theorem. which bounds the number of edges in any edge-minimal k-connected graph. (C) 2008 Elsevier Inc. All rights reserved