20 votes 20 votes 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}$? $\frac{m}{n - 1}$ $m^{n - 1}$ $n^{n - 2}$ $n^{n - 1}$ None of the above Graph Theory tifr2015 graph-theory graph-connectivity + – makhdoom ghaya asked Dec 8, 2015 • retagged Nov 21, 2022 by Lakshman Bhaiya makhdoom ghaya 2.2k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Chhotu commented Nov 16, 2017 reply Follow Share For the same question if it is asked rooted spanning tree then answer would be $n^{n-1}$ 1 votes 1 votes smsubham commented Apr 14, 2018 reply Follow Share Good read: https://en.wikipedia.org/wiki/Cayley%27s_formula 0 votes 0 votes Please log in or register to add a comment.
Best answer 12 votes 12 votes 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}.$ srestha answered Dec 8, 2015 • edited May 27, 2019 by Sukanya Das srestha comment Share Follow See all 2 Comments See all 2 2 Comments reply Tendua commented Dec 8, 2015 i edited by Tendua Dec 8, 2015 reply Follow Share 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 6 votes 6 votes Tendua commented Dec 8, 2015 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.
10 votes 10 votes Number of Spanning trees of a Complete Graph Kn is given by Cayley's theorem = NN-2 https://en.wikipedia.org/wiki/Cayley%27s_formula bhupalreddy answered Dec 11, 2015 bhupalreddy comment Share Follow See all 0 reply Please log in or register to add a comment.