Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to find an efficient method of detecting whether a given graph G has at least two different minimal spanning trees. I'm also trying to find a method to check whether it has at least 3 different minimal spanning trees. The naive solution that I've though about is running Kruskal's algorithm once and finding the total weight of the minimal spanning tree. Later , removing an edge from the graph and running Kruskal's algorithm again and checking if the weight of the new tree is the weight of the original minimal spanning tree , and so for each edge in the graph. The runtime is O(|V||E|log|V|) which is not good at all, and I think there's a better way to do it.

Any suggestion would be helpful, thanks in advance

share|cite|improve this question
As Alex J Best points out, you have posted this question here on StackOverflow. Please note that crossposting between multiple SE sites is highly frowned upon. Try one site first, and if you don't get a satisfactory response, ask a moderator to migrate the question to a different site. – Zev Chonoles May 15 '13 at 22:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.