Gerald J. Tesauro, Jeffrey O. Kephart, et al.
IEEE Expert-Intelligent Systems and their Applications
Let G = (V, E) be a complete n-vertex graph with distinct positive edge weights. We prove that for k ∈ {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 n k - ((k + 1; 2)) elements. This proves a conjecture of Goemans and Vondrák [M.X. Goemans, J. Vondrák, 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. © 2008 Elsevier Inc. All rights reserved.
Gerald J. Tesauro, Jeffrey O. Kephart, et al.
IEEE Expert-Intelligent Systems and their Applications
Chandra Chekuri, Jan Vondrák, et al.
STOC 2011
Richard Arratia, Béla Bollobás, et al.
Discrete Applied Mathematics
Don Coppersmith, Gregory B. Sorkin
Random Structures and Algorithms