Spannig trees

Question

For a complete graph with 10 vertices, The number of spanning trees is at least_____?

Comments

Minimum can be 1 because every graph has atleast 1 spanning tree

---

Minimum number of spannig tree(s) is found by applying Kirchhoff's theorem.

Refer- https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem

---

@iarnav

where is it mentioned that it gives minimum spanning tree ?

i am not able to find....sorry might have overlooked

Answer 1

Exactly 10⁸.

Comments

This is the answer of maximum possible.But as per the question at least?

---

There is no concept of at least MST's

---

@sonu

The question asks Spanning tree, not MST so it will be same as given in answer above.

There is a difference between the number of Minimum spanning tree and the Minimum number of spanning tree.

---

i think answer will be.. 9

this is complete graph then every vertex connected to other n-1 vertex so minimum spanning tree 9

Answer 2

511

# mst in complete graph<=$2^{n-1^{}}-1$

from classical data structures by Samanta debasis