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:

enter image description here

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

  • 2
    $\begingroup$ 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. $\endgroup$
    – Juho
    Jan 22, 2017 at 9:11
  • $\begingroup$ I'm thinking maybe because of this special form I might find a better algorithm than kruskal and prim. $\endgroup$ Jan 22, 2017 at 9:35
  • $\begingroup$ You could start by making a list of all spanning trees. How do they look? $\endgroup$ Jan 22, 2017 at 9:59
  • $\begingroup$ I'm not sure how to answer this question... $\endgroup$ Jan 22, 2017 at 10:46
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Jan 22, 2017 at 21:46

1 Answer 1


That recursive algorithm is wrong, although it was an interesting attempt to improve established algorithms on specialized graphs.

Here is a counterexample with $n=3$.

A counterexample that shows a recursive algorithm for MST on a special form of graph is incorrect http://graphonline.ru/en/?graph=TZUJEcOjSrisGJnY
The graph above was drawn at https://graphonline.ru/en

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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