Exactly k MSTs: How Many Vertices Suffice?

In this work, we study the problem of finding a weighted graph with exactly k minimum spanning trees (MSTs, in short) while minimizing the number of vertices. While finding a graph with k MSTs is easy, finding such a graph with the minimum number of vertices remains an interesting open problem. Recently, Stong [15] proved an upper bound within \(\log k\) multiplicative factor of the minimum. In this work, we prove the following results which make further progress on this problem: