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

Gregory B. Sorkin, Angelika Steger, Rico Zenklusen

Let $G=(V,E)$ be a complete $n$-vertex graph with distinct positive edge weights. We prove that for $k\in \{1,2,...,n-1\}$, the set consisting of the edges of all minimum spanning t…