recategorized by
1,332 views
5 votes
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}$
recategorized by

1 Answer

0 votes
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

Related questions

7 votes
7 votes
1 answer
2
vishal chugh asked Jan 18, 2018
2,137 views
The number of distinct minimum spanning trees for the weighted graph shown below is ___________.
0 votes
0 votes
2 answers
3
Nidhi Budhraja asked Aug 31, 2018
734 views
Q1) Why is the path between a pair of vertices in a minimum Spanning tree of an undirected graph not the shortest( minimum weight) path?
7 votes
7 votes
2 answers
4
Lakshman Bhaiya asked Jan 15, 2018
6,001 views
Consider a complete bipartite graph with ‘m’ and ‘n’ vertices. If m = 4, n = 4, then the number of spanning trees of graph are ________.