TIFR CSE 2015 | Part B | Question: 11

Question

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}$?

• A. $\frac{m}{n - 1}$
• B. $m^{n - 1}$
• C. $n^{n - 2}$
• D. $n^{n - 1}$
• E. None of the above

Comments

For the same question if it is asked rooted spanning tree then answer would  be $n^{n-1}$

---

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

Answer 1

Answer will be (C) 

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}.$

Comments

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

---

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.

Answer 2

Number of Spanning trees of a Complete Graph K_n is given by Cayley's theorem = N^N-2

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