# Graph theory - number of spanning trees generalisation [duplicate]

I'm trying to generalise the number of spanning trees of a complete graph after deletion of any edge. That is, I'm trying to find $$\tau (K_n - e)$$ For $$n$$ number of vertices and we are deleting one edge $$e$$.

So far, I know that $$\tau(K_1) = 1$$, $$\tau(K_2) = 1$$, $$\tau(K_3) = 3$$, $$\tau(K_4) = 16$$, and $$\tau(K_5) = 125$$.

My intuition is that it is equal to $$\frac{\tau(K_n)}{2}$$, because I tried this on $$K_n$$, and found $$8$$ spanning trees.

• Does $\frac{\tau(K_2)}2$ contradict your assumption? $\tau(K_2)=1$ but $\tau(K_2-e)=0\neq \frac12$. – Steve Schroeder Apr 19 '19 at 23:00
• This worked for $n=4$, so I am assuming there is the disclaimer that this only works for $K_{\geq 4}$. – Jeffery Rice Apr 19 '19 at 23:06
• Have you considered $\tau(K_5)=125$? If $\tau(K_5-e)=\frac{\tau(K_5)}{2}$, then $\tau(K_5-e)=62.5$. Although, it's not possible to have half of a spanning tree. Maybe there's more to the formula? – Steve Schroeder Apr 19 '19 at 23:12
• What if you use the deletion contraction algorithm? – Phicar Apr 19 '19 at 23:17
• @SteveSchroeder, that's what I'm thinking. I need help finishing the formula. – Jeffery Rice Apr 20 '19 at 0:29