Problem #4 - How many spanning trees are there of the wheel graph for n >=
4?
This as it turns out is a hard problem, however it is not impossible and
I would like to see if there are people in this class that are resourceful
enough to solve it. I will make this a bonus problem on the homework
and it will not be graded. However if you wish to try the problem there
are two possible approaches that I think might work.
The first is to find a recurrence on the number of spanning trees of W_n
with n vertices in terms of the spanning trees of W_{n-1} and W_{n-2}. The
way I would recommend that you try this is to look at the number of spanning
trees that do not include the last vertex in the picture below and then the
last vertex must have an edge either to the center vertex, or to vertex 2
or to vertex n-1. This isn't the complete story, but it is a start.
Once you have the recurrence, solving it is a much more difficult problem,
but then perhaps you can use other tools to help you guess the answer.
The other approach I would use is to count the number of spanning trees that
have k edges on the outside wheel where 0 <= k <= n-2 (since there
must be at least one edge to the center vertex). This might be hard,
but I was able to use it to get the first 3 values (BTW, the first one must
be 16 since W_4 is the complete graph on 4 vertices). If S_{n,k} are
the number of spanning trees of W_n with k edges around the outside and n-k-1
edges from the center vertex then the total number of spanning trees will
be S_{n,0} + S_{n,1} + .... + S_{n,n-2}.
Back to the Math 3260 page
