Given the complete graph $K_9$, how would you find the number of spanning trees that have exactly one vertex with degree 5? I am a first-year student studying CS. This question was discussed in our Discrete Maths class.
I tried solving it by making one vertex fixed and it has a degree of 5 which could be 5 other vertices and I am left with 3 vertices. Then I applied (8 choose 3) on various scenarios but couldn't come to a proper answer.
Start with the vertex of degree 5 (call it A) and its 5 neighbours (call them B, C, D, E, F). 3 more vertices are then going to be attached to B, C, D, E, F.
First, suppose that all 3 remaining vertices are connected to the same vertex, say B (connected possibly via other two, but not through A). How many ways are there to do it?
Second, suppose that two of the remaining 3 vertices are connected to B and one to C. How many ways are there to do it?
Third, explore other options (there are not many of them).
Sum the counts to get the answer.