687 views

Let $K_{n}$ be the complete graph on $n$ vertices labeled $\left\{1, 2,\dots ,n\right\}$ with $m=\frac{n (n - 1)}{2}$ edges. What is the number of spanning trees of $K_{n}$?

1. $\frac{m}{n - 1}$
2. $m^{n - 1}$
3. $n^{n - 2}$
4. $n^{n - 1}$
5. None of the above.

retagged | 687 views
+1
For the same question if it is asked rooted spanning tree then answer would  be $n^{n-1}$
0

e.g. for $K_4$ no. of spanning tree will be $16$.

Number of Spanning trees of a Complete Graph $K_{n}$ is given by Cayley's theorem = $n^{n-2}.$

by Veteran (119k points)
edited
+5
can u plz derive it. i also know the formula but for the first time i thought of deriving it.. but can't get the logic
0
this may be hit and try. any logical way of thinking, there is not that much of time there. what i thought is.

every vertex will have 2 choices to choose , as there will be (n-1) edges. every internal node have the choice to select any 2. as internal node will be having two edges so (n-1) (n-2) choices, while the 2 starting and end edge have (n-1) choice.

but can't get the formula.

Number of Spanning trees of a Complete Graph Kis given by Cayley's theorem = NN-2

https://en.wikipedia.org/wiki/Cayley%27s_formula

by (119 points)