Checking if v is a leaf in MST

Question

I have this question:

Given undirected graph G = (V,E), V ∋ v and non-negative weights W find if there is a minimum spanning tree (MST) where v is a leaf and if there is, return it.

I thought about finding the MST using prim algorithm and check if v is a leaf in it. If v isn't a leaf I will find the second MST and check on it. The problem is the time complexity will be too high. I am sure there is another way to solve this problem but I don't know how. Can you please give me some clue on how to approach this question?

Answer 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.