2
$\begingroup$

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

$\endgroup$

1 Answer 1

3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ so does it mean that if I repeat this process for every vertex will i get an answer? Like could you please clarify if I can proceed counting them in this way? Thank you. $\endgroup$
    – Sj2704
    Feb 19 at 4:59
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 19 at 5:05
  • $\begingroup$ thank you so much $\endgroup$
    – Sj2704
    Feb 22 at 5:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .