Doubt

Question

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

Answer 1

i think u have asked the question in a wrong way... u must have asked for the range.

why?

because atleast bounds the graph from one side but at the same time it means there is no upper bound on that .

for k=10 we have 10⁸  spanning trees. and if u say we can have atleast 1 means that there should have been possibility for 10¹⁰ spanning trees also for complete graph with 10 vertices which is impossible.

so your question must have been as:

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

soln=1 and that too when upper bound is not defined i mean its close to infinity for the given graph.

Answer 2

Remeber this : - formula for number of spanning tree in a  complete graph  Kn = n^(n-2)

k10 = 10^(8)

Comments

I know this formula for complete graph and if not complete we can apply Kirchoff law to find max number of spanning tree. But in question it is asking for atleast.

---

I think it should be 1?

Answer 3

N^(N-2) for Kn