I need to know how many different spanning trees of $K_n \setminus e$ are there. $K_n \setminus e$ is a graph created by removing one of the edges of a full graph $K_n$.
Well as we all know the number of spanning trees of a full graph is $n^{n-2}$. But graphs fulfill the deletion-contraction rule, meaning that $\tau$ being the number of spanning trees fulfills the following equality.
$\tau(K_n)-\tau(K_n / e)=\tau(K_n \setminus e)$, where $K_n / e$ is a graph made by joining two vertices at the end of edge $e$ and connecting it to all neigbours of edges that lie on $e$. But $K_n / e$ is $K_{n-1}$, right? It has $n-1$ vertices and each an every one of them connects to each other. Therefore $\tau(K_n \setminus e)=n^{n-2}-(n-1)^{n-3}$, right?
Or does deletion contraction rule not apply to simple graphs?