mayank0802's blog

Counting Trees??
By mayank0802, history, 5 years ago, In English

How many different trees can be formed with N nodes?? I read somewhere it is N ^ (N — 2), But doesn't find any proof? May anyone elaborate how it is N ^ (N — 2).

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://www-math.mit.edu/~djk/18.310/18.310F04/counting_trees.html

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -18 Vote: I do not like it

Is this formula is approximation??

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

This problem solution "number of spanning trees in labeled complete graph is $$$n^{n-2}$$$", is called Cayley's Formula, which is famous in graph theory field.

There is a famous proof by Heinz Prüfer (1918) which uses Prüfer Code. But we can able to count number of spanning trees in any undirected simple graph $$$G$$$ via determinant of matrix. This way is called Kirchhoff's Theorem.

→ Reply