Hi, I have this question in one of my assignments. Normally I would use an adjacency matrix (a very big one) to solve these kinds of questions but the hint makes me believe the professor wants me to solve this in a different way. I see no mention in the lectures of why cycles of length 4 have any significance in counting the number of spanning trees so I'm wondering if anyone can help me out with maybe a theorem or lemma that I'm missing? I'm not looking for the answer, just the tools to each the answer because right now I am at a loss. The hint is throwing me off a lot.
Thanks for any help.
Edit: The picture is a bit blurry. The hint says "Consider 5 cases depending on how many edges of the cycle of length 4 you keep."
I’ll expand on the hint a bit.
Suppose that you remove all $4$ edges of the $4$-cycle. What’s left is a $16$-cycle; how many labelled spanning trees does it have?
Now suppose that you remove only $3$ of those $4$ edges: you have a $5$-cycle and a $13$-cycle that share one edge. How many more edges must you remove to get a spanning tree? How many labelled spanning trees can you get in this case?
There are three more cases, and they’re a bit harder, but the principle is the same for all of them: you have to remove just enough edges to break every cycle.