I am using Kruskal's algorithm to build minimum-spanning-trees. I would like to know, given that my total set of edges has size
N, if there is a bounding number of edges in the resulting MST, i.e. a size
M smaller than
N that determines the maximum number of edges in the MST. Or otherwise, if in general no such bounds exists. (Background: I want to allocate an array for the resulting MST in advance, and would like to avoid having to resize it.)
A second, related question: If I have a graph G and a corresponding MST (via Kruskal) from this, and I remove edges from G and rebuild the MST (with the same algorithm), is it safe to assume that the new MST can never have more edges than the old one, i.e. it can only ever shrink?
Edit: If these assumptions do not hold, would any of them hold if an additional property is that the graph G is fully connected?