Number of spanning trees in a graph with a vertex of degree N

Question

I was given the following question on an assignment and had no idea how to solve it(without laplacian matrices), so naturally, I got it wrong. The answer is supposed to be found using combinatorics. The question is below.

Given a complete graph that is provided below, find the number of spanning trees in the graph if vertex 10 were to have a degree of 1 or if vertex 10 had a degree of 4.

https://i.stack.imgur.com/2xveL.png

So, is there a formula to deal with a question like this(using combinatorics)? The question also stated that I should know that the number of spanning trees in a complete graph is: $$n^{n-2}$$

I found that the answer for degree 1 is: $$9^{9-2}=9^7=4782969$$ For degree 4 I have no idea.

Answer 1

The pictured graph is $K_{10}$ Consider the case where vertex $10$ is of degree $1$. There is one edge $e$ incident on vertex $10$ and it must be in the spanning tree. If we delete $e$ from the graph, the graph that remains is a $K_9$ and has $9^7$ spanning trees. Each of these spanning trees, together with edge $e$, gives a spanning tree of the whole graph. So the answer is $9^7$.

The question is harder when the degree is $4$ because, while you must have at least one of the edges incident on vertex $10$, you can have $2,3,\text{ or }4$ of them. Also, when you delete those edges, you don't necessarily have a spanning tree of the remaining graph.

Good luck.

Answer 2

Like many problems about spanning trees of $K_n$, this one is best solved by Prüfer codes.

The $10^8$ spanning trees of $K_{10}$ corresponds to strings of $8$ integers from $1$ to $10$. A key fact about the bijection is that it maps spanning trees in which the $i^{\text{th}}$ vertex has degree $d$ to strings in which $i$ appears $d-1$ times.

So the answer is $9^8$ (not $9^7$) when vertex $10$ has degree $1$, because then you are choosing strings of $8$ integers from $1$ to $9$, and $\binom{8}{3}9^5$ when vertex $10$ has degree $4$.

(By the way, it is very easy to see that the answer for degree $1$ cannot be $9^7$. If so, we would have at most $10 \cdot 9^7$ trees in which any vertex is a leaf, by symmetry - but $10 \cdot 9^7 < 10^8$, and so you would have some trees left over that don't have any leaves at all, which is impossible.)

---

The above assumes you're looking for a spanning tree of $K_n$ in which vertex $10$ has some fixed degree.

If you're instead modifying $K_n$ by deleting some edges incident to vertex $10$ until it has that degree, and then finding all spanning trees, we can still use the above to find the answer, but it takes a bit of work.

Let $\tau_d(G)$ denote the number of spanning trees of a graph $G$ in which vertex $10$ has degree $d$. Let $H$ denote the graph obtained from $K_{10}$ by deleting vertices out of vertex $10$ until it has degree $4$.

Then by symmetry, $\tau_d(H) : \tau_d(K_{10})$ is the same ratio as $\binom{4}{d} : \binom{9}{d}$, since we have $\binom 4d$ ways to pick $10$'s neighbors in $H$ and $\binom 9d$ ways to pick them in $K_{10}$. We can compute $\tau_1(K_{10}) = 9^8$, $\tau_2(K_{10}) = \binom81 9^7$, $\tau_3(K_{10}) = \binom82 9^6$, and $\tau_4(K_{10}) = \binom83 9^5$ by looking at Prüfer codes, and use the ratio to compute $\tau_1(H) + \tau_2(H) + \tau_3(H) + \tau_4(H)$, the number we're interested in.