# 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.

## marked as duplicate by Misha Lavrov graph-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Apr 20 at 0:55

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• 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 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 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 at 23:12
• What if you use the deletion contraction algorithm? – Phicar Apr 19 at 23:17
• @SteveSchroeder, that's what I'm thinking. I need help finishing the formula. – Jeffery Rice Apr 20 at 0:29