# Finding minimum spanning tree of a special form graph

I'm trying to find an efficient algorithm that will find me the minimum spanning tree of an undirected, weighted graph of this particular form: My idea was a recursive solution: Suppose the algorithm recieve the graph with n as a parameter,

if n==2 then:
take the lower cost path between vo-->v1-->v2 and v0-->v2
if n==1 then:
take the lower cost path between v0-->v2-->v1 (if v2 exists) and v0-->v1
else:
- recursivly call the algorithm for n-1
- take the lower cost edge between v0-->vn and v(n-1)-->vn


I'm really not sure wheather this algorithm is correct, i was trying to prove this by induction and got a bit stuck at the base, which got me thinking maybe the algorithm is flawed.

Any suggestions would be much appreciated.

• There are (very) efficient algorithms for finding the MST of any graph; why are these not enough? By the way, your graph is known as a fan: it is a path on n vertices with a dominating vertex added. – Juho Jan 22 '17 at 9:11
• I'm thinking maybe because of this special form I might find a better algorithm than kruskal and prim. – wannabe programmer Jan 22 '17 at 9:35
• You could start by making a list of all spanning trees. How do they look? – Yuval Filmus Jan 22 '17 at 9:59
• I'm not sure how to answer this question... – wannabe programmer Jan 22 '17 at 10:46
• We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. – D.W. Jan 22 '17 at 21:46

Here is a counterexample with $$n=3$$. All edges weigh 2 except that the rightmost two edges, $$(v0,v3)$$ and $$(v2,v3)$$ weigh 1. The recursive algorithm will pick only one edge from the rightmost two edges while an MST must include both of them.
By the way, I cannot understand clearly the description of the algorithm in the case of $$n=1$$ and in the case of $$n=2$$. Fortunately (or unfortunately), that does not affect this answer since the counterexample depends only on the "else" branch of the algorithm, which is described clearly.