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.

  • $\begingroup$ Does $\frac{\tau(K_2)}2$ contradict your assumption? $\tau(K_2)=1$ but $\tau(K_2-e)=0\neq \frac12$. $\endgroup$ – Steve Schroeder Apr 19 '19 at 23:00
  • $\begingroup$ This worked for $n=4$, so I am assuming there is the disclaimer that this only works for $K_{\geq 4}$. $\endgroup$ – Jeffery Rice Apr 19 '19 at 23:06
  • $\begingroup$ 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? $\endgroup$ – Steve Schroeder Apr 19 '19 at 23:12
  • $\begingroup$ What if you use the deletion contraction algorithm? $\endgroup$ – Phicar Apr 19 '19 at 23:17
  • $\begingroup$ @SteveSchroeder, that's what I'm thinking. I need help finishing the formula. $\endgroup$ – Jeffery Rice Apr 20 '19 at 0:29

Browse other questions tagged or ask your own question.