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?


By definition a spanning tree must have $n-1$ edges.

If you remove edges and the graph remains connected, then again, a spanning tree must have $n-1$ edges.

If you remove edges and the graph is disconnected then you will not be able to make a spanning tree for the whole graph but rather you will be able to get a Spanning Forest.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.