How many different trees can be made from a graph

Question

$n$ is an even number. There is a cycle with $n$ vertices, with vertices being labeled from 1 to $n$. When edge is drawn between 1 and $n/2+1$, how many spanning trees can be made from the graph?

Answer 1

This is an extremely specific setting to do this, so we should be able to just count outright how many labelled spanning trees of this graph there are (in general, this may be a difficult question I'd have to think about). Convince yourself that in this graph, we must remove two edges to be able to form a tree (you can think of this graph has having "two" cycles in this sense). Each labelled spanning tree can be formed in this way as well. Thus we have a bijection between the number of labelled spanning trees and the number of ways we can remove two edges of this graph to make the graph acyclic.

So how many ways can we remove these edges? If we choose the chord at all, we have $n$ choices for the other edge. If we do not choose the chord at all, we must choose one edges from each "side" of the graph (either side of the chord), which gives us $\frac{n}{2} \cdot \frac{n}{2}$ choices. (Look this over and draw pictures so that this argument makes sense to you. After that, ask for clarification if necessary.) Then we have $n + \frac{n^2}{4}$ choices total, and thus this many labelled spanning trees.