# Number of spanning trees for $K_n-e$

As the title suggests, I want to calculate the number of spanning trees in $$K_n - e$$ where $$K_n$$ is the complete graph on $$n$$ vertices and $$e$$ is any edge. The answer to this problem is $$(n-2)*(n)^{n-3}$$ and i know one method to do this. My actual question is regarding one of my approaches which is wrong. So let's pick any vertex of the graph, say $$v_1$$ and delete any edge for it. now it has $$n-2$$ edges and through this i can reach any of the vertex. Now all the remaining vertices form a $$K_{n-1}$$ graph and these would have $$(n-1)^{n-3}$$ spanning trees so the total spanning trees would be $$(n-2)*(n-1)^{n-3}$$. Where am i exactly going wrong and is it possible to proceed with this approach? Thank you

Your method counts only the spanning trees where $$v_1$$ is a leaf. A spanning tree of $$K_n - e$$ does not necessarily consist of a spanning tree of $$K_n - v_1$$ plus an edge to $$v_1$$ other than $$e$$.
• Repeating this process for every vertex gives us two problems: (1) if we consider a vertex that's not an endpoint of the deleted edge, then deleting it leaves $K_{n-1}-e$, making us solve the problem recursively; (2) to avoid double-counting, we need to take an inclusion-exclusion type sum over which vertices are leaves at the same time. We could probably get somewhere this way, but it will leave a complicated sum for us to simplify at the end; it is not a good approach. Feb 19 at 5:05