Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

f.nasim's blog

How many spanning trees?
By f.nasim, 16 years ago, In English
How many different spanning trees are possible in a graph with n vertices? Also explain the calculation.Thanks in advance.
  • Vote: I like it
  • 0
  • Vote: I do not like it

16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
If I'm not mistaken, here is what you need: http://en.wikipedia.org/wiki/Kirchhoff's_theorem .
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
It depends on what we consider as different tree, i.e. is vertices numbered or not
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
n^(n-2)
→ Reply