How many spanning trees can we make from a complete graph?

Question

assume we have a complete graph with 'n' vertices. what is the formula for counting all possible spanning trees?

Answer 1

Sounds like a homework problem, haha :-) This is actually a problem in matrix algebra. You want to look up something called the "matrix tree theorem" to research this. The answer by the way is n^(n-2), that is n to the power n-2.

So for a complete graph with 3 vertices you have 3^1=3 spanning trees. For 4 vertices you have 4^2 = 16 spanning trees, for 5 vertices you have 5^3 = 125 spanning trees. For 6 vertices you should get 1296 spanning trees.