How many spanning trees we can build using 26 different nodes that have at least 8 nodes whose degree is exactly 4?

Question

What's the number of spanning trees we can build using 26 different nodes that have at least 8 nodes whose degree is exactly 4?

I hope to get well detailed answer if possible.

---

Update: I'm looking for answer and not only hints since it's hard

Answer 1

I will get you started. I'm not sure how elaborate a full solution would be.

A tree with $26$ vertices has $25$ edges, so the sum of the vertex degrees is $50$. If $8$ vertices have degree $4$, the sum of the vertex degrees of the remaining $18$ vertices is $18$, so the tree must have $18$ leaves.

Call a vertex with $i$ leaves as neighbors a vertex of type $i$, for $i=0,1,2,3$. (Obviously, there can't be any that have $4$ leaves as neighbors.) Say there are $n_i$ vertices of type $i$ for $i=0,1,2,3$. Then we have, $$\begin{align} n_0+n_1+n_2+n_3&=8\\ n_1+2n_2+3n_3&=18 \end{align}$$ So one approach is to find the solutions to these equations in non-negative integers, and see what graphs can be constructed.

Here is one example. We have the solution $$n_=2,n_1=0,n_2=0,n_3=6$$ A type $0$ cannot be adjacent to four type $3$ nodes, because there would be no way to add further nodes to the tree. Therefore the type $0$ nodes are adjacent, and each must be adjacent to $3$ type $3$ nodes, so there is only one tree with these parameters.

It's your turn now.