The number of spanning trees of $W_4$ I need to find the number of spanning trees of $W_4$ (wheels with 5 vertices), can anyone tell me how ?
I guess that the number of spanning trees is 45 spanning trees. I'm not sure how to get this. I still not able to figure out for these  figures. Thanks!
 A: Here’s a rough sketch of $W_4$:
               1  
              /|\  
             / | \  
            2——3——4  
             \ | /  
              \|/  
               5

There are slicker, more sophisticated ways to count the spanning trees, but this graph is small enough that you can count them by brute force if you organize the counting intelligently. Here is one possible way to do it.
Every spanning tree must have at least one radial edge, i.e., an edge incident at the hub vertex, $3$.


*

*Is there a spanning tree that has all four of the radial edges $13,23,43$, and $53$? Yes, exactly one, that looks like a $+$ sign. We can’t add any edges to that without introducing a cycle.

*How many spanning trees are there with exactly $3$ of the $4$ radial edges? To begin with, how many are there with the edges $13,23$, and $43$, but not the edge $53$? A tree with $5$ vertices has $5-1=4$ edges, so we can add only one edge, and it has to connect up vertex $5$. We’ve ruled out the edge $53$, but either of the edges $25$ and $45$ would work, so there are $2$ spanning trees with the edges $13,23$, and $43$, but not the edge $53$. By symmetry it doesn’t matter which of the $4$ radial edges we disallow. For instance, there are also $2$ spanning trees with the edges $13,23$, and $53$, but not $43$. In short, for each choice of $3$ of the $4$ edges radiating from the hub there are $2$ spanning trees, so there are $\binom43\cdot2=8$ spanning trees with exactly $3$ edges incident at the hub.

*Now we’ll count the spanning trees with exactly $2$ radial edges. There are two possibilities: the edges can be adjacent, like $13$ and $23$, or they can be opposite each other, like $13$ and $53$. There are $4$ pairs of adjacent radial edges and $2$ pairs of opposite radial edges. If we have an adjacent pair, like $13$ and $23$, we have to connect up the vertices $4$ and $5$ without using the edges $43$ or $53$. It’s not hard to see that there are exactly $3$ ways to do this: we can have the edge $45$ with exactly one of the two edges $25$ and $14$, or we can have both of the edges $25$ and $14$. Thus, the $4$ pairs of adjacent radial edges account for $4\cdot3=12$ spanning trees. What about the opposite pairs of radial edges, say $13$ and $35$? In order to connect up vertex $2$, we must use exactly one of the edges $12$ and $24$, and in order to connect up vertex $4$, we must use exactly one of the edges $14$ and $45$. Those two-way choices can be made independently, so each opposite pair of radial edges produces $2^2=4$ spanning trees. There are $2$ such pairs, so they account for $2\cdot4=8$ spanning trees. The grand total of spanning trees with $2$ radial edges is therefore $12+8=20$.

*The last step is to count the spanning trees that have exactly one radial edge. Say that edge is $13$; in how many ways can we connect up vertices $2,4$, and $5$ without using any of the edges $23,43$, or $53$? That means that we can use only edges on the circumference of the wheel, and we have to use $3$ of them, since we have to end up with $4$ edges in our spanning tree. It’s not hard to check that we can use any $3$ of them, so there are $\binom43=4$ spanning trees whose only radial edge is $13$. By symmetry there are $4$ spanning trees for each possible choice of a single radial edge, and there are $4$ radial edges, so there are $4\cdot4=16$ spanning trees with exactly one radial edge.
Putting the pieces together, we find a total of $1+8+20+16=45$ spanning trees.
