1
$\begingroup$

I had this question on my final exam so sadly I don't have the question but as far as I remember, the question was saying:

How many minimum spanning trees does a graph with 20 edges have.

I know that we can find minimum spanning trees with algorithms like Prim's algorithm etc. But how can we know the total number of minimum spanning trees in a graph with no figure given in the question (text only)?

$\endgroup$
3
$\begingroup$

I'm hoping you misremembered the question, as the number of MSTs (minimum spanning trees) is not uniquely determined by the number of edges. It depends on what edges are and are not present and also what their weight's are.

For example, if the graph has 21 vertices and 20 edges, then it is a tree and it has exactly one MST. On the other hand, if it has seven vertices and 20 edges, then it is a clique with one edge deleted and, depending on the edge weights, it might have just one MST or it might have literally thousands of them.

(A clique on seven vertices has 21 edges, which is only one more than your graph is allowed. If all the edge weights were the same, every subtree would be an MST and, by Cayley's formula, there are $7^5=16807$ different trees with seven vertices.)

$\endgroup$
  • $\begingroup$ Yeah sadly i dont remember the question very well but your reply gave me the idea thanks for your reply. $\endgroup$ – onur cevik Jan 18 '17 at 13:55
1
$\begingroup$

You cannot know that if the number of edges is the only information you have. It would minimally require a global layout of the graph (thus, edge weights and which nodes are connected) to solve.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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