# Wrong Solution for Spanning tree with chosen leaves problem

Suppose that we're given a connected, undirected graph $$G = (V, E)$$ with edge weights $$w_e$$ and a subset of vertices $$U \subset V$$. We want to find the lightest spanning tree in which the nodes of $$U$$ are leaves (they may be other leaves as well). We want to do so in $$O(|E|\log(|V|))$$ time.

I was reading: Spanning tree with chosen leaves But I think the solution is totally wrong:

1. Generate an induced graph G' containing the vertices V'=V-U and the edges E' not involving the vertices in U
2. Apply Kruskal's algorithm to get T'= MST(G')
3. If T' does not exist then the solution does not exist
4. Construct an edge set E" = (u, v) where u belongs to U and v does not belong to U
5. Apply Kruskal's algorithm on E" by adding edges to T'
6. Return T'

As a counter example, consider the following graph $$G=(V,E)$$ where: $$V={1,2,3,4}, E={(1,2),(2,3),(3,4),(2,4)}$$ and $$U={4}$$ where the weight of edges connected to 4 is -100 and 1 for the rest.

It's clear there is no MST in G where vertex 4 is leaf. But the suggested algorithm above will return a solution...

• OK. Do you have a question? What is your question? We are a question-and-answer site, so we require you to articulate a specific question.
– D.W.
May 13 at 7:32
• Hello, unregistered user! You are wrong. If you register an account, I will tell you why. May 13 at 18:16