5 5 votes How do we come up with this formula for number of spanning tree of a n vertex complete graph Kn= $n^{n-2}$ Algorithms minimum-spanning-tree algorithms graph-theory + – Mahendra Singh Kanya 1.9k views answer comment Share Follow Print See all 3 Comments 3 3 Comments reply Mk Utkarsh commented Mar 18, 2018 i edited by Mk Utkarsh Mar 18, 2018 reply Follow flag https://en.wikipedia.org/wiki/Cayley%27s_formula Narsingh Deo - Page 52-54 and 240 0 0 replyShare akshat sharma commented Mar 18, 2018 reply Follow flag For graph Kn #spaning tree=nn-1(cayley law) For complete Bipartite Graph Kmn #spaning tree=mn-1nm-1 For more informationhttps://kam.mff.cuni.cz/~atcagc14/materialy/Lecture_2_Spanning_trees.pdf 0 0 replyShare G Shaheena commented Mar 27, 2018 reply Follow flag simply try with 3 nodes, 4 nodes..etc, you can get formula 0 0 replyShare Please log in or register to add a comment.
0 0 votes There are many proofs for these formula : 1) By finding a one to one correspondence of this problem with another one (Prufer sequence) and then counting the number of Prufer sequences. Reference : https://www.math.uchicago.edu/~may/VIGRE/VIGRE2006/PAPERS/Casarotto.pdf 2) For a more intuitive proof by the method of double counting you can check "Proofs from THE BOOK, written by Martin Aigner Günter M. Ziegler" Reference : https://books.google.co.in/books/about/Proofs_from_THE_BOOK.html?id=KvQr9l0wgf8C&redir_esc=y ArjuMlu answered Mar 19, 2018 ArjuMlu comment Share Follow 0 reply Please log in or register to add a comment.
