Number of spanning trees in undirected simple graph What is the number of spanning trees in an undirected simple graph?


My attempt:

Let $m$ be the number of edges in a simple graph, and let $n$ be the number of vertices.

Then number of spanning trees is $\binom{m}{n-1}$ minus the number of cycles of length $n-1$.

I read on Wikipedia that the number of spanning trees in the complete graph $K_n$ is $n^{n-2}$.

According to the formula I stated above, it should be $\binom{n(n-1)/2}{n-1} - \binom{n}{n-1} (n-1)!$.

How do I show that this is equal to $n^{n-2}$ for $K_n$?
You cannot show this since it isn't true. I encourage you to try out some actual numbers (e.g. $n=2$) and see for yourself that the numbers don't match. The problem is that what you should be subtracting is not the number of cycles of length $n-1$, but rather the number of collections of $n-1$ edges which contains at least one cycle. Such a collection need not be a cycle of length $n-1$.

In addition, the formula for the number of cycles of length $n-1$ is wrong. The number is $n(n-2)!$ rather than your $n(n-1)!$, and even this formula is only valid for $n \geq 4$ (for smaller $n$ there are no such cycles). However, even after replacing $n(n-1)!$ by $n(n-2)!$, the numbers don't match.