Checking if v is a leaf in MST

Solution 1:

The problem with "generate all MSTs and check if v is a leaf in any of them" is that the number of MSTs in a graph can be enormous: it could be as many as n ** (n-2) where n is the number of nodes.

A better way is to observe that all MSTs of a given graph have the same total weight. So a more efficient algorithm could work like this:

• Apply a standard algorithm to find an MST of G. Let total_weight be its total weight.
• Apply a standard algorithm to find an MST of G - v, i.e. the graph without the node v. Let mst_without_v be this MST, and let weight_without_v be its total weight.
• If v has an edge of weight total_weight - weight_without_v, then add this edge to mst_without_v and return it. Otherwise, return null.

If the algorithm returns a graph, then it is an MST of G because it spans (G - v) + v = G, it is a tree (because it was formed from a tree with one leaf added), and it has the correct total weight.

If the algorithm returns null, then no MST of G exists where v is a leaf. Otherwise, deleting v from such an MST would give an MST of G - v with the wrong total weight.